• Binary Search

    Binary Search

    Introduction:

    Binary Search is quicker than the linear search. However, it cannot be applied on unsorted data structure. The binary search is based on the approach divide-and-conquer. The binary search starts by testing the data in the middle element of the array. This determines target is whether in the first half or second half. If target is in first half, we do not need to check the second half and if it is in second half no need to check in first half. Similarly we repeat this process until we find target in the list or not found from the list.

    To implement binary search method, the elements must be in sorted order. Search is performed as follows:

    • The key is compared with item in the middle position of an array
    • If the key matches with item, return it and stop
    • If the key is less than mid positioned item, then the item to be found must be in first half or array, otherwise it must be in second half of array.
    • Repeat the procedure for lower (or upper half) of array until the element is found.

    Algorithm of Binary Search:

    Binary_Search(a,key,lb,ub)

    begin
    Step 1:  [initialization]
    lb=0
    ub=n-1;
    Step 2:  [search for the item]

    Repeat through step 4 while lower bound(lb) is less than upper bound.

    Step 3:  [obtain the index of middle value]
    mid = (lb+ub)/2
    Step 4:  [compare to search for item]

      if(key < a[mid]) then

      ub=mid-1

      otherwise if( key > a[mid]) then

      lb=mid+1;

      otherwise if(key==a[mid])

    Write “match  found”

      return (mid)

    return Binary_Search(a,key,lb,ub)

    Step 5:  [unsuccessful search]

      Write “match not found”

    Step 6:  [end of algorithm

    Binary Search Recursive Program Code

    Example – Binary Search on Array/List using C Language

    #include<stdio.h>

    int bsearch(int [ ],int,int);void main( )
    {
    int a[20],pos,n,k,i;
    clrscr();
    printf(“\nEnter the n value:”);
    scanf(“%d”,&n);
    printf(“\nEnter elements for an array:”);for(i=0;i<n;i++)
    scanf(“%d”,&a[i]);
    printf(“\nEnter the key value:”);
    scanf(“%d”,&k);
    pos=bsearch(a,n,k);

    if(pos!= -1)
    printf(“Search successful, element found at position %d”,pos);
    else
    printf(“Search unsuccessful, element not found”);

    getch( );
    }

    int bsearch(int a[ ],int n, int k)
    {
    int lb=0,ub,mid;
    lb=0;
    ub=n-1;

    while(ub>=lb)
    {
    mid=(lb+ub)/2;

    if(k<a[mid])
    ub=mid-1;

    else if(k>a[mid])
    lb=mid+1;

    else if(k==a[mid])
    return(mid);
    }

    return -1;

    }

    Appreciate my work :Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedInPin on PinterestShare on RedditShare on StumbleUponShare on TumblrDigg thisShare on YummlyShare on VKFlattr the authorBuffer this page

One Responseso far.

  1. lalit says:

    very nice job….

Leave a Reply

Your email address will not be published. Required fields are marked *