Binary Search

Concept

Binary search needs a sorted array as input.

In binary search , each time an array is divided into 2 subarrays with mid as midpoint of the array.If we find our key at mid we stop.

Else , if our key is greater than key at mid, then our key must lie in the upper half of the array.So we eliminate the lower subarray and choose the upper subarray to find our key.

Else , if key is lesser than key at mid then our key must lie in the lower half of the array.So we eliminate the upper subarray and choose the lower subarray to find our key.

We stop when we find our key at mid or if key is not found.

Algorithm

Initialize low = 0 , high = n-1 , mid = (low+high)/2

Until low<=high and key not found

        Compare key with key(mid).

        If key matches , return mid.

        else if key > key(mid)
            low = mid + 1

        else
            high = mid - 1

if key is not found return -1 

Code

#include<stdio.h>

void binsearch(int[],int);

int main()
{
    int a[15],pos,n,i;

    printf("\n Enter no of elements ");
    scanf("%d",&n);

    printf("\n Enter elements ");

    for(i=0;i<n;i++)
        scanf("%d",&a[i]);

    binsearch(a,n);

    return 0;
}

void binsearch(int a[],int n)
{
    int low = 0 , high = n-1 , key , mid = (low + high)/2 ,comp = 1;

    printf("\n Enter key to be searched ");
    fflush(stdin);
    scanf("%d",&key);

    while(low<=high && key != a[mid])
    {
        comp++;

        if(key<a[mid])
            high = mid - 1;
        else
            low = mid + 1;

        mid = (low + high)/2;
    }

    if(a[mid]==key)
    {
        printf("\n Element found at position = %d",mid + 1);
        printf("\n Comparisons = %d",comp);
    }
    else
        printf("\n Element not found");
}

O/P

More 

Time Complexity of binary search