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 (SIZE1).

ITEM is the data that needs to be searched.

beg, last and mid are variables of type int(eger).
Here is the algorithm:

LET beg = L AND last = U

REPEAT STEPS 3 THROUGH 6 TILL beg<=last

mid = ( (beg+last)/2)

IF AR[mid] = ITEM THEN ITEM IS AT POSITION mid BREAK THE LOOP

IF AR[mid] < ITEM THEN beg = mid+1

IF AR[mid] > ITEM last = mid1

END OF LOOP

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=mid1 for // data in descending order if(ar[mid]>item) last=mid1;// should be beg=mid+1 for // data in descending order } // search end if(!(ar[mid]==item)) cout<<"\nSearch unsuccessfull!"; cout<<endl; }
GoodBye guys!
Do check back for updates!
Related Articles:
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).
ReplyDeleteYeah I'm using an interval of 6 for the loop but if you look closely, there is this line:
ReplyDeletemid=((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.