# Implement Binary Search on a Sorted Array

Given a sorted array of integers, return the index of the given value.

We'll cover the following

## Statement

We are given an array of integers, nums, sorted in ascending order, and an integer value, target. If the target exists in the array, return its index. If the target does not exist, then return -1.

The binary search divides the input array by half at every step. After every step, either we find the index we are looking for, or we discard half of the array.

## Example

Given the following sorted array, if the target’s value is 9, the binary search returns 2.

### Sample input

nums = [1, 3, 9, 10, 12]
target = 9


### Expected output

2


## Try it yourself

#include <iostream>using namespace std;int BinarySearch(int nums[], int target, int length) {	//TODO: Write - Your - Code	return -1;}

## Solution 1: Iterative

In the iterative approach, here is how the algorithm works:

• At each step, consider the array between low and high indices.
• Calculate the mid index.
• If the element at the mid index is equal to the target value, we return mid.
• If the element at mid is greater than the target:
• Change the index high to mid - 1.
• The value of low remains the same.
• If the element at mid is less than the target:
• Change low to mid + 1.
• The value of high remains the same.
• When the value of low is greater than the value of high, this indicates that the target doesn’t exist. Hence, -1 is returned.
#include <iostream>#include <vector>using namespace std;int BinarySearch(int nums[], int target, int length) {	int low = 0;	int high = length - 1;	while (low <= high) {		// Finding the mid using floor division		int mid = low + ((high - low) / 2);		// Target value is present at the middle of the array		if (nums[mid] == target) {			return mid;		}		// Target value is present in the low subarray		else if (target < nums[mid]) {			high = mid - 1;		}		// Target value is present in the high subarray		else if (target > nums[mid]) {			low = mid + 1;		}	}	// Target value is not present in the array	return -1;}int main() {	vector<vector<int> > nums = {		{}, {0, 1}, {1, 2, 3}, {-1, 0, 3, 5, 9, 12}, {-1, 0, 3, 5, 9, 12}};	vector<int> sizes = {0, 2, 3, 6, 6};	vector<int> targets = {12, 1, 3, 9, 2};	for (int i = 0; i < nums.size(); i++) {		cout << i + 1 << ". Array to search: ";		// A custom function to neatly print the list		PrintList(nums[i]);		cout << "   Target: " << targets[i] << endl;		int index = BinarySearch(nums[i].data(), targets[i], sizes[i]);		if (index != -1) {			cout << "   " << targets[i] << " exists in the array at index " << index << endl;		} else {			cout << "   " << targets[i] << " does not exist in the array so the return value is " << index << endl;		}		cout << "------------------------------------------------------------------------------------------------------\n" << endl;	}}

### Time complexity

The time complexity of this solution is logarithmic, $O(log \space n)$.

### Space complexity

The space complexity of this solution is constant, $O(1)$.

## Solution 2: Recursive

In this solution, we will implement the binary search algorithm recursively. At each step, the search function calls itself using either the right half or the left half of the sorted array.

Let’s look at another example below:

#include <iostream>using namespace std;int BinarySearchRec(int nums[], int key, int low, int high) {	if (low > high) {		return -1;	}	// Finding the mid using floor division	int mid = low + ((high - low) / 2);	// Target value is present at the middle of the array	if (nums[mid] == key) {		return mid;	}	// Target value is present in the low subarray	else if (key < nums[mid]) {		return BinarySearchRec(nums, key, low, mid - 1);	}	// Target value is present in the high subarray	else {		return BinarySearchRec(nums, key, mid + 1, high);	}}int BinarySearch(int nums[], int target, int length) {	return BinarySearchRec(nums, target, 0, length - 1);}int main() {	vector<vector<int> > nums = {		{}, {0, 1}, {1, 2, 3}, {-1, 0, 3, 5, 9, 12}, {-1, 0, 3, 5, 9, 12}};	vector<int> sizes = {0, 2, 3, 6, 6};	vector<int> targets = {12, 1, 3, 9, 2};	for (int i = 0; i < nums.size(); i++) {		// A custom function to neatly print the list		cout << i + 1 << ". Array to search: ";		PrintList(nums[i]);		cout << "   Target: " << targets[i] << endl;		int index = BinarySearch(nums[i].data(), targets[i], sizes[i]);		if (index != -1) {			cout << "   " << targets[i] << " exists in the array at index " << index << endl;		} else {			cout << "   " << targets[i] << " does not exist in the array so the return value is " << index << endl;		}		cout << "------------------------------------------------------------------------------------------------------\n" << endl;	}}

### Time complexity

The time complexity of this solution is logarithmic, $O(log \space n)$.

### Space complexity

The space complexity of this solution is logarithmic, $O(log \space n)$ because the recursive approach consumes memory on the stack.