Binary Search

Given a sorted array of integers and a target value, find out if a target exists in the array or not in O(log(n)) time. If target exists in the array, print index of it.


For example,
 
Input:

arr[] = [2, 3, 5, 7, 9]
target = 7

Output: Element found at index 3

 
Input:

arr[] = [1, 4, 5, 8, 9]
target = 2

Output: Element not found


 
A simple solution would be to perform Linear search on the given array. It sequentially checks each element of the array for the target value until a match is found or until all the elements have been searched. Worst case time complexity of this approach is O(n) as it makes at most n comparisons, where n is the length of the array. This approach don’t take advantage of the fact that array is sorted.

 
How can be perform better?

The idea is to use Binary Search. Binary Search is a divide and conquer algorithm. Like all divide and conquer algorithms, Binary Search first divides a large array into two smaller sub-arrays and then recursively (or iteratively) operate the sub-arrays. But instead of operating on both sub-arrays, it discards one sub-array and continue on the second sub-array. This decision of discarding one sub-array is made in just one comparison.

So Binary Search basically reduces the search space to half at each step. By search space we mean sub-array of given array where the target value is located (if present in the array). Initially, the search space is the entire array and binary search redefine the search space at every step of the algorithm by using the property of the array that it is sorted. It does so by comparing the mid value in the search space to the target value. If the target value matches the middle element, its position in the array is returned else it discards half of the search space based on the comparison result.

Let us track the search space by using two index – start & end. Initially, start = 0 and end = n-1 (as initially whole array is our search space). At each step, we find the mid value in the search space and compares it with target value. There are three cases possible –

Case 1: If target = A[mid], we return mid.
Case 2: If target < A[mid], we discard all elements in the right search space including the mid element i.e. A[mid..high]. Now our new high would be mid – 1.
Case 3: target > A[mid], we discard all elements in the left search space including the mid element i.e. A[low..mid]. Now our new low would be mid + 1.

 

We repeat the process until target is found or our search space is exhausted. Let’s understand this by taking a example. Let

arr = [2, 3, 5, 7, 8, 10, 12, 15, 18, 20]
target = 7

binary-search-1
 


binary-search-2


 
binary-search-3

 
Iterative C++ implementation –
 

Download   Run Code

Output:

Element found at index 1

 

We can easily convert above iterative version of the binary search algorithm to recursive one. Below is the recursive version.

 
Recursive C++ implementation –
 

Download   Run Code

Output:

Element found at index 1

 

Performance

We know that at each step of the algorithm, our search space reduces to half. That means if initially our search space contains n elements, then after one iteration it contains n/2, then n/4 and so on..

n -> n/2 -> n/4 -> … -> 1

Suppose after k steps our search space is exhausted. Then,

n/2k = 1
n = 2k
k = log2n

Therefore, time complexity of binary search algorithm is O(log2n) which is very efficient. Auxiliary space used by it is O(1).
 

Overflow

signed int in C/C++ takes up 4 bytes of storage i.e. It allows storage for integers between -2147483648 to 2147483647 (Note that some compilers might take up 2 bytes storage as well. The exact value can be find by cout << sizeof(int);).

So if (low + high) > 2147483647, integer overflow will happen.

int mid = (low + high)/2; // overflow can happen

To avoid integer overflow, we can use any of the below expressions –

int mid = low + (high – low)/2; OR
int mid = high – (high – low)/2;

Now, low + (high – low) / 2 or high – (high – low) / 2 always computes a valid index halfway between high and low, and overflow will never happen even for extreme values.

 

Binary Search in C++ Standard Libraries

C++ STL library provides binary_search() function that is defined in header “algorithm”. It returns true if target is found otherwise it returns false. Below is its implementation –

Download   Run Code

Output:

Element found

 

Suggested Read: Binary search vs Ternary Search

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂