Ad

Monday, June 25, 2007

Binary Search: A Method of Searching

Binary Search method is popular for searching a specific item in an ordered array (sorted). It can perform the search in minimum possible comparisons, but it needs the array to be sorted in any order.

Practically, it is used when the data is itself sorted initially or needs to be sorted for other activities also. This is because you don’t want to first sort the data and then use binary search, in that case use of linear search would be practical.

Binary Search Algorithm

Suppose,

  • The array to be AR[SIZE] having SIZE number of elements.

  • L is the index number of the lower element. We take it to be 0.

  • U is the index number of the upper (last) element. It will be (SIZE-1).

  • ITEM is the data that needs to be searched.

  • beg, last and mid are variables of type int(eger).

Here is the algorithm:

  1. LET beg = L AND last = U
  2. REPEAT STEPS 3 THROUGH 6 TILL beg<=last
  3. mid = ( (beg+last)/2)
  4. IF AR[mid] = ITEM THEN
           ITEM IS AT POSITION mid
           BREAK THE LOOP
  5. IF AR[mid] < ITEM THEN
           beg = mid+1
  6. IF AR[mid] > ITEM
           last = mid-1
  7. END OF LOOP
  8. IF AR[mid] = ITEM THEN
           SEARCH IS UNSUCCESSFULL

Here is the example program:

  // BINARY SEARCH PROGRAM
  // example program in C++

  #include<iostream.h>

  void main(void)
  {
   int beg, last, mid, item, i;
   int ar[5];

   // sorted data needs to be input
   cout<<"enter sorted data:\n";
   for(i=0; i<5; i++)
     cin>>ar[i];

   cout<<"enter search term:";
   cin>>item;

   // as per array
   beg=0;
   last=5;

   // binary searching starts
   while(beg<=last)
     {
      // calculate the middle
      // of the array section
      mid=((beg+last)/2);

      if (ar[mid]==item)
        {
         cout<<"\n\n";
         cout<<item<<" found at index no. "<<mid;
         break;
        }

      if(ar[mid]<item)
        beg=mid+1;// should be beg=mid-1 for
        // data in descending order

      if(ar[mid]>item)
        last=mid-1;// should be beg=mid+1 for
        // data in descending order
     }
     // search end

   if(!(ar[mid]==item))
     cout<<"\nSearch unsuccessfull!";

   cout<<endl;
  }

Good-Bye guys!

Do check back for updates!

Related Articles:

2 comments:

  1. Anonymous4:37 PM

    You declare an array of five elements. However, you use an interval of six during your search procedure. Number of elements (cardinality) of a set: b - a + 1 (5 - 0 + 1).

    ReplyDelete
  2. Yeah I'm using an interval of 6 for the loop but if you look closely, there is this line:

    mid=((beg+last)/2);

    if (ar[mid]==item)

    Also beg and last are getting changed in each iteration hence loop will never run from 0 through 5 (6 times) in any case.

    Hope that helps.

    ReplyDelete

You are free to comment anything, although you can comment as 'Anonymous' it is strongly recommended that you supply your name. Thank You.

Please don't use abusive language.