Connecting Tech Pros Worldwide Help | Site Map
bytes > topic > c > insights

Binary Search

Newbie
  
Join Date: Jun 2008
Posts: 9
#1   Jun 15 '08
Binary search is used to locate a value in a sorted list of values.
It selects the middle element in the array of sorted values, and compares it with the target value; that is the key we are searhing for in the array.
If it islower than the target value then the search is made after that middle element and till the end of the array. If it is equal then the target value is found and the middle is returned. Otherwise, search is made from the beginning of the array till middle -1. If the lower limit is larger than the upper limit, the ones that determine the search area, then the target value is not in the array.

I present an example code for a binary search function.


Expand|Select|Wrap|Line Numbers
  1.  
  2. /**
  3.  *
  4.  *
  5.  *    FILE: bsearch.h
  6.  *
  7.  *
  8.  *    Description:
  9.  *
  10.  *        Function prototype for binarySearch function.
  11.  *
  12.  *
  13.  */
  14.  
  15.  
  16.  
  17. #ifndef _bsearch_h
  18.  
  19.  
  20.  
  21. #define _bsearch_h
  22.  
  23.  
  24.  
  25.  
  26.  
  27. /**
  28.  *
  29.  *    Synopsis:
  30.  *
  31.  *        int binarySearch( int a[], int key, int size )
  32.  *
  33.  *
  34.  *    Description:
  35.  *
  36.  *        Function binarySearch performs a binary search in a 
  37.  *        sorted array a searching for a key.
  38.  *
  39.  *
  40.  *    Parameters:
  41.  *
  42.  *        a[]: sorted array of integers.
  43.  *
  44.  *        key: key to be searched for in a[].
  45.  *
  46.  *        size: size of a[].
  47.  *
  48.  *
  49.  *    Assertions:
  50.  *
  51.  *        none.
  52.  *
  53.  *
  54.  *    Returns:
  55.  *
  56.  *        Function binarySearch returns -1 if key is not in a[].
  57.  *        Otherwise in returns the i, for which a[ i ] == key.
  58.  *
  59.  *
  60.  */
  61. int binarySearch( int a[], int key, int size );
  62.  
  63.  
  64.  
  65.  
  66.  
  67. #endif 


Expand|Select|Wrap|Line Numbers
  1. /**
  2.  *
  3.  *
  4.  *    FILE: binarySearch.c
  5.  *
  6.  *
  7.  *    Description:
  8.  *
  9.  *        File contains binarySearch functions declared in bsearch.h file.
  10.  *
  11.  *
  12.  */
  13.  
  14.  
  15.  
  16.  
  17.  
  18. #include "bsearch.h"
  19.  
  20.  
  21.  
  22.  
  23.  
  24. /**
  25.  *------------------------------------------------------------
  26.  *
  27.  *    Function _binarySearch is called by binarySearch function with
  28.  *    low = 0 and high = size - 1, to secure the search boundaries of 
  29.  *    the array.
  30.  *
  31.  *------------------------------------------------------------
  32.  */
  33. static int _binarySearch( int a[], int key, int low, int high );
  34.  
  35.  
  36.  
  37.  
  38.  
  39. int binarySearch( int a[], int key, int size ){
  40.  
  41.  
  42.  
  43.     return ( _binarySearch( a, key, 0, size - 1 ) );
  44.  
  45.  
  46.  
  47. }    //    int binarySearch( int a[], int key, int size )
  48.  
  49.  
  50.  
  51.  
  52. /**
  53.  *------------------------------------------------------------
  54.  *
  55.  *    Search key value in a[].
  56.  *
  57.  *------------------------------------------------------------
  58.  */
  59. static int _binarySearch( int a[], int key, int low, int high ){
  60.  
  61.  
  62.  
  63.     if ( low > high ){
  64.  
  65.  
  66.  
  67.         return ( -1 );                                /** key not found in a[]                                                */
  68.  
  69.  
  70.  
  71.     }
  72.     else{
  73.  
  74.  
  75.  
  76.         int middle = ( low + high ) / 2;
  77.  
  78.  
  79.  
  80.         if ( a[ middle ] == key ){
  81.  
  82.  
  83.  
  84.             return ( middle );                        /** key found in a[]                                                    */
  85.  
  86.  
  87.  
  88.         }
  89.         else if ( a[ middle ] < key ){
  90.  
  91.  
  92.  
  93.             /**
  94.              *
  95.              *    key we are searching is larger than the value of a[ middle ]
  96.              *    and since array is sorted, the search will continue in the side
  97.              *    after the middle index; that is from middle + 1 till high.
  98.              *
  99.              */
  100.             return ( _binarySearch( a, key, middle + 1, high ) );
  101.  
  102.  
  103.  
  104.         }
  105.         else{
  106.  
  107.  
  108.  
  109.             /**
  110.              *
  111.              *    key we are searching is lower than the value of a[ middle ]
  112.              *    and since array is sorted, the search will continue in the side
  113.              *    before the middle index; that is from low till high - 1.
  114.              *
  115.              */
  116.             return ( _binarySearch( a, key, low, middle - 1 ) );
  117.  
  118.  
  119.  
  120.         }
  121.  
  122.  
  123.  
  124.     }
  125.  
  126.  
  127.  
  128. }    //    static int _binarySearch( int a[], int key, int low, int high ) 

Expand|Select|Wrap|Line Numbers
  1. /**
  2.  *
  3.  *
  4.  *    FILE: main.c
  5.  *
  6.  *
  7.  *    Description:
  8.  *
  9.  *        Test binarySearch function.
  10.  *
  11.  *
  12.  */
  13.  
  14.  
  15.  
  16.  
  17.  
  18. #include "bsearch.h"
  19.  
  20.  
  21.  
  22. #include <assert.h>
  23.  
  24.  
  25.  
  26.  
  27.  
  28. /**
  29.  *
  30.  *    Simple check for binarySearch function
  31.  *
  32.  */
  33. int main( void ){
  34.  
  35.  
  36.  
  37.     int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };
  38.  
  39.  
  40.  
  41.     int i;
  42.  
  43.  
  44.  
  45.     for ( i = 0 ; i < 21 ; ++i ){
  46.  
  47.  
  48.  
  49.         assert( binarySearch( a, i, 21 ) == i );
  50.  
  51.  
  52.  
  53.     }
  54.  
  55.  
  56.  
  57.     for ( ; i < 50 ; ++i ){
  58.  
  59.  
  60.  
  61.         assert( binarySearch( a, i, 21 ) == -1 );
  62.  
  63.  
  64.  
  65.     }
  66.  
  67.  
  68.  
  69.     return ( 0 );
  70.  
  71.  
  72.  
  73. }    //    int main( void ) 



Reply

« previous insight | next insight »

Similar C / C++ bytes

/bytes/development

/bytes/it

/bytes/about

We are a network of experts and professionals in IT and software development that help one another with answers to tough questions and share insights. Get the best answers to your questions from over 226,223 network members.

dev questions:
algorithms | asp | asp.net | c/c++ | coldfusion | c# | flash | html/css | java | javascript |
mobile dev | .net | perl | php | python | ruby | software dev | vb.net | visual basic | xml
it questions:
access | apache | careers | db2 | iis | macosx | mysql | networking | oracle | postgresql | sql server | unix | windows

About Bytes | Copyright 1995-2009 BYTES. All rights Reserved