Coderust: Hacking the Coding Interview/

...

/

Implement Binary Search on a Sorted Array

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

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.

g node_key target: 9 array 0 1 2 3 4 1 3 9 10 12 node_key->array:e6

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 n)O(log \space n).

Space complexity

The space complexity of this solution is constant, O(1)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 n)O(log \space n).

Space complexity

The space complexity of this solution is logarithmic, O(log n)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.