Binary Search

[Atos]

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.

 
/**
 *
 *
 *    FILE: bsearch.h
 *
 *
 *    Description:
 *
 *        Function prototype for binarySearch function.
 *
 *
 */
 
 
 
#ifndef _bsearch_h
 
 
 
#define _bsearch_h
 
 
 
 
 
/**
 *
 *    Synopsis:
 *
 *        int binarySearch( int a[], int key, int size )
 *
 *
 *    Description:
 *
 *        Function binarySearch performs a binary search in a 
 *        sorted array a searching for a key.
 *
 *
 *    Parameters:
 *
 *        a[]: sorted array of integers.
 *
 *        key: key to be searched for in a[].
 *
 *        size: size of a[].
 *
 *
 *    Assertions:
 *
 *        none.
 *
 *
 *    Returns:
 *
 *        Function binarySearch returns -1 if key is not in a[].
 *        Otherwise in returns the i, for which a[ i ] == key.
 *
 *
 */
int binarySearch( int a[], int key, int size );
 
 
 
 
 
#endif 

/**
 *
 *
 *    FILE: binarySearch.c
 *
 *
 *    Description:
 *
 *        File contains binarySearch functions declared in bsearch.h file.
 *
 *
 */
 
 
 
 
 
#include "bsearch.h"
 
 
 
 
 
/**
 *------------------------------------------------------------
 *
 *    Function _binarySearch is called by binarySearch function with
 *    low = 0 and high = size - 1, to secure the search boundaries of 
 *    the array.
 *
 *------------------------------------------------------------
 */
static int _binarySearch( int a[], int key, int low, int high );
 
 
 
 
 
int binarySearch( int a[], int key, int size ){
 
 
 
    return ( _binarySearch( a, key, 0, size - 1 ) );
 
 
 
}    //    int binarySearch( int a[], int key, int size )
 
 
 
 
/**
 *------------------------------------------------------------
 *
 *    Search key value in a[].
 *
 *------------------------------------------------------------
 */
static int _binarySearch( int a[], int key, int low, int high ){
 
 
 
    if ( low > high ){
 
 
 
        return ( -1 );                                /** key not found in a[]                                                */
 
 
 
    }
    else{
 
 
 
        int middle = ( low + high ) / 2;
 
 
 
        if ( a[ middle ] == key ){
 
 
 
            return ( middle );                        /** key found in a[]                                                    */
 
 
 
        }
        else if ( a[ middle ] < key ){
 
 
 
            /**
             *
             *    key we are searching is larger than the value of a[ middle ]
             *    and since array is sorted, the search will continue in the side
             *    after the middle index; that is from middle + 1 till high.
             *
             */
            return ( _binarySearch( a, key, middle + 1, high ) );
 
 
 
        }
        else{
 
 
 
            /**
             *
             *    key we are searching is lower than the value of a[ middle ]
             *    and since array is sorted, the search will continue in the side
             *    before the middle index; that is from low till high - 1.
             *
             */
            return ( _binarySearch( a, key, low, middle - 1 ) );
 
 
 
        }
 
 
 
    }
 
 
 
}    //    static int _binarySearch( int a[], int key, int low, int high ) 

/**
 *
 *
 *    FILE: main.c
 *
 *
 *    Description:
 *
 *        Test binarySearch function.
 *
 *
 */
 
 
 
 
 
#include "bsearch.h"
 
 
 
#include <assert.h>
 
 
 
 
 
/**
 *
 *    Simple check for binarySearch function
 *
 */
int main( void ){
 
 
 
    int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };
 
 
 
    int i;
 
 
 
    for ( i = 0 ; i < 21 ; ++i ){
 
 
 
        assert( binarySearch( a, i, 21 ) == i );
 
 
 
    }
 
 
 
    for ( ; i < 50 ; ++i ){
 
 
 
        assert( binarySearch( a, i, 21 ) == -1 );
 
 
 
    }
 
 
 
    return ( 0 );
 
 
 
}    //    int main( void )