Binary Search Algorithm in Array
In this article we will learn to perform Search Operation to locate an element using Binary Search Algorithm in Array.
Binary search is more efficient way to find an element in array as compared to Linear Search. This is because Binary Search Algorithm is based on divide-n-conquer method.
The main requirement of Binary Search Algorithm in array is that it must be sorted in increasing numerical order. It divides the array in two parts and then determines which half part contains the element. Then in the selected half part, it again finds the middle element to divide it in two quarter parts. And then it determines which quarter part contains the element. And so on till we locate the element.
Searching Element Using Binary Search Algorithm in Array
In this example DATA is a sorted array. The variable LB and UB refers to the lower bound and upper bound of an array that is starting and ending of an array respectively. BEG and END is used to store the beginning and ending of the segment. The MID refers to the middle of segment.
The Binary Search Algorithm in Array is as follows
BINARY (DATA, LB, UB, ITEM, LOC)
1. Set BEG = LB , END=UB and MID=(BEG+END)/2 2. Repeat steps 3 and 4 while BEG<=END and DATA[MID] ≠ ITEM 3. If ITEM < DATA[MID], then: Set: END =MID-1 Else: Set: BEG=MID+1 [End If] 4. Set MID=(BEG+END)/2 [End while] 5.If DATA[MID]=ITEM, then: Set: LOC=MID Else: Set LOC= NULL [End If] 6. Exit.
Lets start understanding the meaning of some statements.
MID = (BEG+END) / 2 calculates the location of middle element of segment.
If ITEM < DATA[MID], then ITEM will be in the left half of the segment. So we set END = MID-1
If ITEM > DATA[MID], then ITEM will be in the right half of the segment. So we set BEG = MID+1
In the array given above, we have 9 elements which are arranged in increasing order. Lets search whether 89 is present in this array or not.
|MID= (1+9)/2= 5|
As ITEM > DATA [MID] so Modify the value of BEG
|BEG= 6||MID= (6+9)/2 =7|
So in just two comparisons we found our element. Suppose we try to find same element using linear search then, number of comparisons required will be 7 where as in case of binary search its only 2. Hence binary search algorithm is more efficient than linear search.
Limitation of Binary Search Algorithm in Array
Binary search algorithm requires array to be sorted as well as it requires direct access to the middle element of array.