As input doubles, the maximum number of steps increases by one

Complexity

Time

Space

$O(log(n))$

Split the search space by two on every iteration

Process

Start by searching in the middle

If what you are looking for is smaller than what you find in the middle, restrict search up to the middle

If what you are looking for is bigger than what you find in the middle, restrict search space from middle on

Repeat until you find what you're looking for or your search space has nothing in it

Implementations

JavaScript

functionbinarySearch(target, sortedArray) {
// Start the search space with the entire arraylet lowIndex = 0;
let highIndex = sortedArray.length - 1;
// While the search space has elements in it...while (lowIndex <= highIndex) {
// Grab the middle, acounting for a min (lowIndex)const middleIndex = lowIndex + Math.floor((highIndex - lowIndex) / 2);
const guess = sortedArray[middleIndex];
// Target found!if (guess === target) {
return middleIndex;
}
if (guess < target) {
// Middle is less than target// Adjust search space to second half of current search space
lowIndex = middleIndex + 1;
} else {
// Middle is greater than target// Adjust search space to first half of current space
highIndex = middleIndex - 1;
}
}
return -1;
}