# Implement Binary Search on a Sorted Array

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

## 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 - Codereturn -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.

- Change the index
- If the element at
`mid`

is less than the`target`

:- Change
`low`

to`mid + 1`

. - The value of
`high`

remains the same.

- Change
- 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 divisionint mid = low + ((high - low) / 2);// Target value is present at the middle of the arrayif (nums[mid] == target) {return mid;}// Target value is present in the low subarrayelse if (target < nums[mid]) {high = mid - 1;}// Target value is present in the high subarrayelse if (target > nums[mid]) {low = mid + 1;}}// Target value is not present in the arrayreturn -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 listPrintList(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 divisionint mid = low + ((high - low) / 2);// Target value is present at the middle of the arrayif (nums[mid] == key) {return mid;}// Target value is present in the low subarrayelse if (key < nums[mid]) {return BinarySearchRec(nums, key, low, mid - 1);}// Target value is present in the high subarrayelse {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 listcout << 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.