Binary Search: Algorithm and Examples

What Is Binary Search?

Binary search is an efficient searching algorithm used to find a target value in a sorted collection. Instead of checking every element one by one, binary search repeatedly divides the remaining search range into two parts.

At each step, the algorithm compares the target with the middle element. Based on the comparison, it eliminates the half of the search space that cannot contain the target.

This allows binary search to find an element in O(log n) time in the worst case, making it significantly more efficient than a linear search for large sorted arrays.

Binary Search Example

Consider this sorted array:

[10, 20, 30, 40, 50, 60, 70]

Suppose we want to find 60. Binary search starts by checking the middle element, 40.

Target = 60

[10, 20, 30, 40, 50, 60, 70]
             ^
          middle = 40

Since 60 is greater than 40, the target cannot be in the left half. The algorithm continues with:

[50, 60, 70]
     ^
  middle = 60

The target matches the middle element, so the search is complete.

Why Must Binary Search Use Sorted Data?

Binary search depends on the ordering of the elements. After checking the middle value, the algorithm needs to know which half can safely be discarded.

For example, if the middle element is 40 and the target is 60, a sorted array tells us that values to the left of 40 cannot contain 60.

Sorted:

[10, 20, 30, 40, 50, 60, 70]
             ↑
           middle

Target = 60

Discard:

[10, 20, 30, 40]

Search:

[50, 60, 70]

Without a suitable ordering, this decision cannot be made reliably. In that situation, a normal binary search cannot be applied directly.

The Three Important Positions

An iterative binary search usually maintains three values:

• left — the beginning of the current search range.
• right — the end of the current search range.
• middle — the position checked during the current iteration.

The middle position is commonly calculated using:

middle = Math.floor((left + right) / 2);

Another common formulation is:

middle = left + Math.floor((right - left) / 2);

The second form avoids adding the two indexes directly and is commonly preferred in implementations where integer overflow is a concern.

How Binary Search Narrows the Search Range

After comparing the target with the middle element, there are three possibilities.

Target Equals Middle Element

The target has been found, so the algorithm can return the middle index.

Target Is Smaller

If the target is smaller than the middle element in an ascending array, the right side can be discarded.

Target = 20

[10, 20, 30, 40, 50, 60, 70]
             ↑
           middle

20 < 40

Search the left half.

Target Is Larger

If the target is larger than the middle element, the left side can be discarded.

Target = 60

[10, 20, 30, 40, 50, 60, 70]
             ↑
           middle

60 > 40

Search the right half.

Binary Search Step by Step

Let's search for 73 in the following sorted array:

[11, 23, 35, 47, 59, 71, 73, 86, 98]

The first middle element is 59. Since 73 is greater than 59, the left half is discarded.

[71, 73, 86, 98]
     ^
   middle = 73

The target is now found after only two comparisons. A linear search could have required checking several elements before reaching the same value.

Iterative Binary Search in JavaScript

An iterative implementation uses a loop to repeatedly reduce the search range.

function binarySearch(array, target) {
  let left = 0;
  let right = array.length - 1;

  while (left <= right) {
    const middle = left + Math.floor((right - left) / 2);

    if (array[middle] === target) {
      return middle;
    }

    if (array[middle] < target) {
      left = middle + 1;
    } else {
      right = middle - 1;
    }
  }

  return -1;
}

const numbers = [10, 20, 30, 40, 50, 60, 70];

console.log(binarySearch(numbers, 60));
// 5

console.log(binarySearch(numbers, 25));
// -1

Understanding the Binary Search Loop

The condition left <= right means that the current search range still contains at least one possible position.

When the middle value is smaller than the target, the new left boundary becomes middle + 1 because the middle element has already been checked and cannot be the answer.

Similarly, when the middle value is greater than the target, the new right boundary becomes middle - 1.

Recursive Binary Search

Binary search can also be implemented recursively. Each recursive call works on a smaller search range.

function binarySearchRecursive(array, target, left, right) {
  if (left > right) {
    return -1;
  }

  const middle = left + Math.floor((right - left) / 2);

  if (array[middle] === target) {
    return middle;
  }

  if (array[middle] < target) {
    return binarySearchRecursive(
      array,
      target,
      middle + 1,
      right
    );
  }

  return binarySearchRecursive(
    array,
    target,
    left,
    middle - 1
  );
}

const numbers = [10, 20, 30, 40, 50, 60, 70];

console.log(
  binarySearchRecursive(numbers, 50, 0, numbers.length - 1)
);
// 4

Iterative vs Recursive Binary Search

Both approaches use the same binary search principle, but they differ in implementation and auxiliary space.

Binary Search Time Complexity

Binary search has logarithmic time complexity because the search space is approximately halved after every comparison.

Search space:

n
n / 2
n / 4
n / 8
...
1

The number of times the collection can be divided by two grows logarithmically with its size.

Space Complexity of Binary Search

The iterative implementation requires only a few variables such as left, right, and middle. Therefore, its auxiliary space complexity is O(1).

The recursive implementation uses the call stack for recursive calls, so its auxiliary space is O(log n) in the usual recursive implementation.

Binary Search With Duplicate Values

A standard binary search may return any matching occurrence when duplicate values exist. It does not automatically guarantee the first or last occurrence.

[10, 20, 20, 20, 30, 40]

Target = 20

If an application needs the first occurrence, the algorithm must continue searching toward the left after finding a match. For the last occurrence, it must continue toward the right.

Finding the First Occurrence

function firstOccurrence(array, target) {
  let left = 0;
  let right = array.length - 1;
  let result = -1;

  while (left <= right) {
    const middle = left + Math.floor((right - left) / 2);

    if (array[middle] === target) {
      result = middle;
      right = middle - 1;
    } else if (array[middle] < target) {
      left = middle + 1;
    } else {
      right = middle - 1;
    }
  }

  return result;
}

const numbers = [10, 20, 20, 20, 30, 40];

console.log(firstOccurrence(numbers, 20));
// 1

Binary Search on an Empty Array

An empty array has no valid search range. With right set to array.length - 1, the initial value becomes -1, so the loop is not entered.

const numbers = [];

console.log(binarySearch(numbers, 10));
// -1

Binary Search When the Target Does Not Exist

If the target is not present, the search range eventually becomes empty. When left becomes greater than right, the algorithm can conclude that the target does not exist.

const numbers = [10, 20, 30, 40, 50];

console.log(binarySearch(numbers, 35));
// -1

Binary Search vs Linear Search

Both algorithms can locate values in an array, but they use very different strategies.

Common Binary Search Mistakes

• Using binary search on unsorted data.
• Updating left or right incorrectly.
• Forgetting to exclude the middle element after it has already been checked.
• Using an incorrect loop condition.
• Returning the wrong index when duplicate values exist.
• Failing to handle an empty array.
• Confusing finding any occurrence with finding the first or last occurrence.
• Ignoring whether sorting the data first is worthwhile for the overall workload.

When Should You Use Binary Search?

Binary search is useful when data is maintained in an appropriate sorted order and efficient repeated searching is important. Its logarithmic search complexity becomes especially useful as the number of elements grows.

• The collection is sorted.
• Fast searches are required.
• The collection contains many elements.
• The ordering of the data can be maintained or is already available.
• The search operation is performed frequently.

When Is Linear Search More Appropriate?

Binary search is not always the practical choice. If the data is unsorted, a linear search can be simpler. Sorting an array solely to perform one search may introduce additional work that is not justified by the search itself.

The decision should therefore consider the complete operation: whether the data is already sorted, how often searches occur, how frequently the collection changes, and how large it is.

Binary Search in Real Applications

Binary search is useful in systems where ordered data needs to be queried efficiently. Examples include searching sorted identifiers, locating a value in an ordered numeric collection, finding insertion positions, and solving algorithmic problems that require repeatedly reducing a search range.

The same divide-and-search principle is also used in more advanced algorithmic techniques, including variations that search for boundaries, first or last occurrences, and answers within a numeric range.

Key Takeaways

• Binary search is designed for appropriately sorted data.
• It compares the target with the middle element of the current range.
• Each comparison can eliminate approximately half of the remaining search space.
• The worst-case time complexity is O(log n).
• The iterative implementation uses O(1) auxiliary space.
• The recursive implementation uses O(log n) call-stack space.
• A standard binary search can return an index or -1 when the target is absent.
• Duplicate values require modified logic when the first or last occurrence is needed.
• Sorting requirements should be considered before choosing binary search.