Binary Search

Searching

Given an arbitrary collection of n keys, the only way to determine if a search key is present by examining each element which yields O(n) complexity.
If the collection is organized, searching can be speed up dramatically.

Binary Search

Binary search is a natural divide-and conquer strategy for searching. The idea is to eliminate half the keys from consideration by keeping the keys in a sorted array. If the search key is not equal to the middle element of the array, one of the two sets of keys to the left and to the right of the middle element can be eliminated from further consideration.

Below is the working code in C Language.

#include<stdio.h>
int bsearch(int a[],int size,int elem)
{
        int low=0;
        int up=size-1;
        int mid;
        while(low <= up) {
                mid=(low+up)/2;
                if(a[mid]==elem)
                        return mid;
                else if(a[mid]<elem)
                        low=mid+1;
                else
                        up=mid-1;
        }
        return -1;
}
int main()
{
        int arr[10]={1,2,3,4,5,6,7,8,9,10};
        int pos,srch_elem;
        printf("Enter element to search : ");
        scanf("%d",&srch_elem);
        pos=bsearch(arr,10,srch_elem);
        if(pos == -1)
                printf("%d is not in array\n",srch_elem);
        else
                printf("%d is at location %d\n",srch_elem,pos+1);
        return 0;
}

Here in the above program of binary search there is a bug. The error is in assignment mid = (low+up)/2; it can lead to overflow (in case of array size large approx equal to size of int) and hence should be replaced by mid = low + (up-low)/2 .

The time complexity of binary search is equal to O(logn), which is superior to O(n) approach needed when the keys are unsorted.