JavaScript binary search

Search a sorted numeric array with a shrinking interval.

JavaScript

function binarySearch(values, target) {
  let low = 0, high = values.length - 1;
  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);
    if (values[mid] === target) return mid;
    if (values[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}
console.log(binarySearch([2, 4, 6, 8, 10], 8));
console.log(binarySearch([], 8));
if (binarySearch([2, 4], 3) !== -1) throw new Error("missing");

Output

3
-1

Explanation

Binary search discards half of an ascending sorted array after comparing the middle value. low and high are inclusive bounds.

Math.floor computes an integer midpoint. This version returns any matching index and -1 when the interval becomes empty.

Explore the dry run

Guided walkthroughReady

1function binarySearch(values, target) {

2 let low = 0, high = values.length - 1;

3 while (low <= high) {

4 const mid = low + Math.floor((high - low) / 2);

5 if (values[mid] === target) return mid;

6 if (values[mid] < target) low = mid + 1;

7 else high = mid - 1;

8 }

9 return -1;

10}

11console.log(binarySearch([2, 4, 6, 8, 10], 8));

12console.log(binarySearch([], 8));

13if (binarySearch([2, 4], 3) !== -1) throw new Error("missing");

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Initialize bounds for the first call.	`low = 0, high = 4`	—
Inspect the middle.	`mid = 2, value = 6`	—
6 is below 8, so move low.	`low = 3, high = 4`	—
Inspect index 3.	`mid = 3, value = 8`	—
Return and print the match.	`mid = 3, value = 8`	3
The empty array starts with high=-1; skip the loop and return -1.	`mid = 3, value = 8`	3 -1

Cost and common mistakes

O(log n) time and O(1) auxiliary space.

Do not search unsorted input.
Default array sort compares strings; use a numeric comparator when sorting numbers first.

Try it yourself

Search for 10 in the first array.

Reveal answer and reasoning

The algorithm inspects indices 2, 3, and 4, returning 4.

JavaScript binary search

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading