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

**Iterative C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include <iostream> using namespace std; // Binary search algorithm to return the position of // target x in the array A of size N int BinarySearch(int A[], int N, int x) { // search space is A[low..high] int low = 0, high = N - 1; // iterate till search space contains at-least one element while (low <= high) { // find the mid value in the search space and // compares it with target value int mid = (low + high)/2; // overflow can happen // int mid = low + (high - low)/2; // int mid = high - (high - low)/2; // target value is found if (x == A[mid]) return mid; // if target is less than the mid element, discard all elements // in the right search space including the mid element else if (x < A[mid]) high = mid - 1; // if target is more than the mid element, discard all elements // in the left search space including the mid element else low = mid + 1; } // target doesn't exist in the array return -1; } // main function int main() { int A[] = {2, 5, 6, 8, 9, 10}; int N = sizeof(A)/sizeof(A[0]); int target = 5; int index = BinarySearch(A, N, target); if (index != -1) cout << "Element found at index " << index; else cout << "Element not found in the array"; return 0; } |

**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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include <iostream> using namespace std; // Binary search algorithm to return the position of // target x in the sub-array A[low..high] int BinarySearch(int A[], int low, int high, int x) { // Base condition (search space is exhausted) if (low > high) return -1; // we find the mid value in the search space and // compares it with target value int mid = (low + high)/2; // overflow can happen // int mid = low + (high - low)/2; // Base condition (target value is found) if (x == A[mid]) return mid; // discard all elements in the right search space // including the mid element else if (x < A[mid]) return BinarySearch(A, low, mid - 1, x); // discard all elements in the left search space // including the mid element else return BinarySearch(A, mid + 1, high, x); } // main function int main() { int A[] = {2, 5, 6, 8, 9, 10}; int n = sizeof(A)/sizeof(A[0]); int target = 5; int low = 0, high = n - 1; int index = BinarySearch(A, low, high, target); if (index != -1) cout << "Element found at index " << index; else cout << "Element not found in the array"; return 0; } |

**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/2^{k} = 1

n = 2^{k}

k = log_{2}n

Therefore, time complexity of binary search algorithm is O(log_{2}n) which is very efficient. Auxiliary space used by it is O(1) for iterative implementation and O(log_{2}n) for recursive implementation due to call stack.

**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 –

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include <iostream> #include <algorithm> #include <vector> using namespace std; // main function int main() { vector<int> arr {1, 2, 5, 8, 9}; int target = 2; if (binary_search(arr.begin(), arr.end(), target)) cout << "Element found "; else cout << "Element not found in the vector"; return 0; } |

**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 🙂

## Leave a Reply

> Auxiliary space used by it is O(1).

This is technically false, you use recursion so you need space for the stack frames, so the auxiliary space you are using is equal to max recursion depth. If splitting in 2, this means same as time complexity – O(log_2 n)

Thanks Aleksander for bringing this to our notice. We have updated the post.

Happy coding 🙂

the second picture is false? The mid should be A[2]?