Binary Search

Binary search

By Junaid Ali Siddiqui

What is Binary search?  Suppose

DATA is an array which is sorted in any numerical order or equivalently alphabetically .  Then there is an extremely efficient algorithm called binary search which can be used to find the location LOC of a given ITEM of information in DATA.

General idea about binary search algorithm  

   

Suppose one wants to find the location of some name in a telephone directory or some word in dictionary . Obviously one does not perform a linear search rather one opens the directory in the middle to determine which half contains the name being sought. Then one opens that half in the middle to determine which quarter of the directory contains the name . Then one opens that quarter in the middle to determine which eighth of the directory contains the name &so on. Eventually one finds the location of the name . Since one is reducing the possible locations for it in the directory.

Binary search algorithm In this algorithm  DATA is a sorted array which is sorted in ascending order with lower bound LB & upper bound UB & ITEM is a given item of information to be searched.  The variables BEG , END & MID denote respectively the beginning ,end & middle locations of a segment of elements of DATA.  This algorithm finds the location LOC of ITEM in DATA or sets LOC equal to NULL.

BINARY(DATA,LB,UB,ITEM,LOC) Step 1 : [Initialize segment variables] Set BEG=LB,END=UB & MID=INT((BEG+END)/2). Step 2 : Repeat Steps 3 & 4 while BEG <=END &DATA[MID ]!=ITEM Step 3 : if(ITEM
Remark  Whenever

ITEM does not appear in DATA ,the algorithm eventually arrives at the stage that BEG=END=MID.  Then the next step yeilds END
Complexity of the Binary search algorithm  The

complexity is measured by the number f(n) of comparisons to locate ITEM in DATA where DATA contains n elements.  Observe that each comparison reduce the sample size in half .  Hence we require atmost f(n) comparisons to locate ITEM where 2exp f(n)>n or equivalently f(n)= log2n + 1  That is the running time for the worst case is approximately equal to log2n .  One can also show that the running time for the average case is approximately equal to the running time for the worst case.

Limitations of the binary search algorithm

Since the binary search algorithm is very efficient. Why would one want to use any other search algorithm?  Observe that the algorithm requires two conditions. (a) The list must be sorted. (b) One must have direct access to middle element in any sublist.  This means that one must essentially use a sorted array to hold the data but keeping data in a sorted array is normally very expensive when there are many insertions & deletions.  Accordingly in such situations one may use a different data structure such as link list or binary search tree to store the data.  

Message: Friend ship is just like a snowball easy to make hard to keep .So always be sincere to your friends.

THANK YOU!

Reference: Theory & problems of Data structures by Shaum’s series.