Binary Search Algorithm in Data Structures

The binary search algorithm uses divide and conquer strategy to search an element from a given list. This algorithm works properly if the given list is sorted. The binary search looks for a particular item by comparing the middle most item of the collection. If a match occurs, then the index of the item is returned. If the middle item is greater than the item, then the item is searched in the sub-array to the left of the middle item. Otherwise, the item is searched for in the sub-array to the right of the middle item. This process continues on the sub-array as well until the size of the subarray reduces to zero.

Suppose A is an array which is sorted in increasing numerical order or, equivalently alphabetically. Then, there is an extremely efficient searching algorithm, called ‘binary search’, which can be used to find the location LOC of a given ITEM of information in A.

Algorithm: (Binary Search.) BINARY(A, LB, UB, ITEM, LOC).

Here, A is a sorted array with lower bound LB and upper bound UB, and ITEM is a given item of information. The variable BEG, END, and MID denote respectively, the beginning, end and middle locations of a segment of elements of A. This algorithm finds the location LOC of ITEM in A or sets LOC = NULL.

Step I: [Initialize segment variable.]

Set BEG := LB, END := UB and MID := INT((BEG+END)/2).

Step II: Repeat steps 3 and 4 while BEG <= END and A[MID] != ITEM:

Step III: If A[MID] > ITEM, then:

Set END := MID-1.

Else: 

Set BEG:= MID+1.

[End of If structure.]

Step IV: Set MID := INT((BEG+END)/2).

[End of step 2 loop.]

Step V: If BEG > END, then:

Set LOC:= NULL.

Else: 

Set LOC := MID.

Step VI: Exit.