Binary Search
What it is and why you might need it

General description

binary search (alias logarithmic search) is a searching technique that follows the divide and conquer strategy, which means to break down a bigger problem in smaller chunks and solve them individually. In the case of binary search, a bigger array will be programmatically divided into smaller chunks without the need to create a new array.

Requirements

There is one important requirement for binary search to work as intended:

The elements of the input array have to be in sorted order.

Approach

// sorted array of length 15
const array = [1, 14, 24, 35, 44, 57, 64, 71, 79, 80, 85, 99, 105, 144, 190];
               |               |                                         |
              low             key                                       high

const low = 0; // the lower limit of currently possible range
const high = array.length - 1; // the upper limit of currently possible range
const key = 44; // the value we want to find

Algorithm:

formular to calculate the current middle value:

middle = (low + high) / 2

example: (0 + 14) / 2 = 7

IMPORTANT: Take the floor value, which is in above case: 7.
If the result would be 7.5 (15/2) - take 7

Steps

1. calculate the middle value by dividing the sum of high and low by 2
2. check if array[mid] === key
3. if array[mid] > key, continue search left
   • high = mid-1
4. if array[mid] < key, continue search right
   • low = mid+1
5. repeat steps 1 - 4 until array[mid] === key

Code example

/**
 * @description Binary search algorithm implementation
 *
 * Time complexity:
 * min O(1)
 * max O(log(n))
 *
 * The time required to search depends on the height of the tree which is
 * log(n) as log2(16) = 4, as 2^4 = 16
 *
 *           8          (1
 *         /   \
 *        4     12      (2
 *       / \    / \
 *      2   6  10 14    (3
 *
 * @param array searchable and sorted array
 * @param key the value that has to be found
 */

function binarySearch(array: number[], key: number): number {
	// set initial values
	let low = 0;
	let high = array.length - 1;
	let middle = calculateMiddle(low, high);

	// main implementation
	while (array[middle] !== key) {
		// case if not found at all
		if (high === low && array[high] !== key) return -1;

		if (array[middle] > key) {
			high = middle - 1;
		}
		if (array[middle] < key) {
			low = middle + 1;
		}
		middle = calculateMiddle(low, high);
	}
	return middle;
}

/**
 * @description helper function to calculate the current middle
 * @param low the lower bound in the current search range
 * @param high the higher bound in the current search range
 */
function calculateMiddle(low: number, high: number): number {
	return Math.floor((low + high) / 2);
}

Explained

in above code example, first we set the initial values low and high. We use the helperfunction calculateMiddle to get the middle value by applying the mentioned formular. In a while loop, we first check the exit condition for non existing elements. If the current middle value is bigger than the key, the searched value must be in the left hand side of the sorted array (ascending order). Therefore we can set the higher bound to the current middle minus one.

If the current middle value is smaller than the key, the searched value must be on the right hand side of the sorted array. Therefore we can set the lower bound to the current middle plus one.

This continues until an element is found or the exit condition is met.