Binary Search Algorithm in Array

Binary Search Algorithm

Binary Search Algorithm

Binary Search Algorithm in Array is part of Learning Data Structure Series. In the previous article of Linear Search Algorithm in Array we learnt to locate an element in an array linearly.

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

Example:

Index 1 2 3 4 5 6 7 8 9
Value 15 17 25 55 60 77 89 90 99

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.

Index 1 2 3 4 5 6 7 8 9
Value 15 17 25 55 60 77 89 90 99
BEG=1 END=9 MID= (BEG+END)/2
MID= (1+9)/2= 5

 

As ITEM > DATA [MID] so Modify the value of BEG

Index 1 2 3 4 5 6 7 8 9
Value 15 17 25 55 60 77 89 90 99
BEG=MID+1 END=9 MID= (BEG+END)/2
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.

Searching Algorithms in Learning Data Structure Series will follow with Sorting Algorithms. In next article we will learn Bubble Sort Algorithm in Array.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *