# Implement Binary Search on a Sorted Array

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

## Statement

**Binary search** is an efficient algorithm used to find the position of a target value within a sorted array. It repeatedly divides the array in half, comparing the middle element with the target. Depending on the comparison, it narrows the search to the left or right half of the array, until the target is found or the subarray size becomes zero.

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; otherwise, return `-1`

.

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

## Binary search applications

**Search engines:**It helps to efficiently search through large indexed databases.**Libraries:**Locating books in a catalog organized by some order.**Databases:**Quick retrieval of records from sorted data.**Genome Analysis:**Finding sequences within large genetic databases.**E-commerce:**Searching through sorted product listings.