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:
";
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<<"

";
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<<"
Search unsuccessfull!";

cout<<endl;
}

Good-Bye guys!


Do check back for updates!


Related Articles:


Related Posts by Categories

0 comments:

Post a Comment