Skip to content

Binary Search

In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.

Binary search can be used to solve a wider range of problems, such as finding the next-smallest or next-largest element in the array relative to the target even if it is absent from the array.

Problems

The binary search algorithm solves two kinds of problems:

  1. to check if a target element is in an array;
  2. to find the element that is bigger(less) than or equal to a target.

And if you think deeper, you can use the method for second problem to solve first one. That is, to find the element \(\ge\) the target and check if the element found is the target.

Code

The main idea of binary search algorithm is to divide the search range into two parts:

  1. Target must not exit part, which will not be considered in next search process;
  2. Target may exit part, which will be considered in next search process.

There are two templates for the code, one for left end and one for right:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// Left end
// Devide range [l, r] to [l, mid] and [mid + 1, r], and l locates at (mid + 1)
int bs(int a[], int l, int r) {
  while (l < r) {
    int mid = l + r >> 1;
    if (resultl_is_in(mid)) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  return l;
}

// Right end
// Devide range [l, r] to [l, mid - 1] and [mid, r], and l locates at (mid)
int bs(int a[], int l, int r) {
  while (l < r) {
    // avoid the case [l, r] = [0, 1]
    int mid = l + r + 1 >> 1;
    if (is_result_in(mid)) {
      l = mid;
    } else {
      r = mid - 1;
    }
  }
  return l;
}

Complexity

In binary search process, algorithm half the search range every time, so for an array of length \(N\), the worst time complexity is \(O(log(N))\).

The iteration version implementation costs \(O(1)\) space complexity. But for the recursive version, the space complexity is \(O(log(N))\).

Practice

There are many kinds of problems, but if the range of problem can be divided into two parts:

  1. Must not contain the target;
  2. May contain the target;

it can be solved with binary search.

Binary Search in an Array

Binary Search in a Range

Binary Search with Implicit Relations

Reference