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:

• 
  

  
  String Searching Function in C++