Data Structure $ Algorithms Binary Search ...

DATA STRUCTURE & ALGORITHMS BINARY SEARCH DATA STRUCTURE & ALGORITHMS

What is a Binary Search?

A search algorithm with Ο(log n) run-time complexity, and working on the principle of divide and conquer is Binary Search. The data should be collected in the form of sorted in order to ensure proper working of this algorithm.

The binary search works by searching a item by comparing the middle item of the data collection. The index of the matched item is then returned. If the middle item is greater than a particular item, then it will search in the left sub-array of the middle item. Otherwise, the item is searched in the right sub-array of the middle item.

How Binary Search Works?

Most importantly, the target array has to be sorted for the binary search to work. The working of the binary search is shown in the pictorial illustration.

For instance, the location of value 31 is searched using binary search.

First, determine half of the array by using this formula −

1

mid = low + (high - low) / 2

2

​

Here it is, 0 + (9 - 0 ) / 2 = 4 (integer value of 4.5). So, 4 is the mid of the array.

Now compare the value stored at location 4, with the value being searched, i.e. 31. It is observed that the value at location 4 is 27, which is not a match. As the value is greater than 27 and a sorted array, so the target value must be in the upper portion of the array.

Change the low to mid + 1 and find the new mid value again.

1

low = mid + 1

2

mid = low + (high - low) / 2

3

​

New mid is 7 now. Compare the value stored at location 7 with our target value 31.

The value stored at location 7 is not a match, rather it is less than what we are looking for. So, the value must be in the lower part from this location.

Hence, calculate the mid again. This time it is 5.

Compare the value stored at location 5 with our target value, and it is found that it is a match.

Now conclude that the target value 31 is stored at location 5.

Binary search halves the searchable items and thus reduces the count of comparisons to be made to very less numbers.

Pseudocode

The pseudocode of binary search algorithms is −

1

Procedure binary_search

2

A ← sorted array

3

n ← size of array

4

x ← value to be searched

5

Set lowerBound = 1

6

Set upperBound = n

7

while x not found

8

if upperBound < lowerBound 

9

EXIT: x does not exists.

10

set midPoint = lowerBound + ( upperBound - lowerBound ) / 2

11

if A[midPoint] < x

12

set lowerBound = midPoint + 1

13

if A[midPoint] > x

14

set upperBound = midPoint - 1

15

if A[midPoint] = x 

16

EXIT: x found at location midPoint

17

end while

18

end procedure

19

​