JavaScript · Course navigation

JavaScript binary search

Search a sorted numeric array with a shrinking interval.

On this page

Before you start

Functions, loops, and array indexing.

Search a sorted numeric array with a shrinking interval.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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.

Code example

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

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

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

Behind the scenes

How JavaScript processes this code

A JavaScript engine parses and runs the source. A function body runs when the function is called. console.log writes to the console.

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.