Skip to content

Binary Search

This page briefly introduces binary search, ternary search derived from the bisection method, and binary answer.

Definition

Binary search (English: binary search), also known as half-interval search (English: half-interval search) or logarithmic search (English: logarithmic search), is an algorithm used to find a specific element in a sorted array.

Process

Take searching for a number in an ascending array as an example.

Each time, it examines the middle element of the current part of the array. If the middle element is exactly the one being searched for, the search process ends; if the middle element is less than the value being searched for, the left side will only be smaller and will not contain the element being searched for, so the search continues on the right side; similarly, if the middle element is greater than the value being searched for, the search continues on the left side.

Properties

Time Complexity

The optimal time complexity of binary search is \(O(1)\).

The average and worst-case time complexities of binary search are both \(O(\log n)\). This is because during the binary search process, the algorithm halves the search interval each time, so for an array of length \(n\), at most \(O(\log n)\) searches are performed.

Space Complexity

The space complexity of the iterative version of binary search is \(O(1)\).

The space complexity of the recursive version (without tail call elimination) of binary search is \(O(\log n)\).

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
int binary_search(int start, int end, int key) {
  int ret = -1;  // Returns -1 if data is not found
  int mid;
  while (start <= end) {
    mid = start + ((end - start) >> 1);  // Direct averaging may overflow, so use this algorithm
    if (arr[mid] < key)
      start = mid + 1;
    else if (arr[mid] > key)
      end = mid - 1;
    else {  // Finally check equality because most searches are either greater or less
      ret = mid;
      break;
    }
  }
  return ret;  // Single exit
}

Note

Refer to Compiler Optimizations #Bit Operations Instead of Multiplication. For signed \(n\), when you can guarantee \(n\ge 0\), n >> 1 uses fewer instructions than n / 2.

Minimizing the Maximum

Note that the term "sorted" here is generalized. If one side of an array satisfies a certain condition while the other side does not, it can also be considered as a form of sorting (if satisfying the condition is regarded as \(1\) and not satisfying as \(0\), at least for this dimension of the condition, it is sorted). In other words, binary search can be used to find the maximum (or minimum) value that satisfies a certain condition.

To find the minimum possible case of the maximum value that satisfies a certain condition (minimizing the maximum), the initial idea is to enumerate the "maximum" as the answer from small to large, and then check if it is valid. If the answer is monotonic, binary search can be used to find the answer more quickly. Therefore, to use binary search to solve such "minimizing the maximum" problems, the following three conditions must be met:

  1. The answer lies within a fixed interval;
  2. It may not be easy to find a value that meets the condition, but it should be relatively easy to determine whether a given value meets the condition;
  3. Feasible solutions satisfy a certain monotonicity with respect to the interval. In other words, if \(x\) meets the condition, then \(x + 1\) or \(x - 1\) also meets the condition. (This ensures the monotonicity mentioned above.)

Of course, maximizing the minimum is similar.

The C++ standard library implements the function std::lower_bound, which finds the first element not less than a given value, and the function std::upper_bound, which finds the first element greater than a given value. Both are defined in the <algorithm> header.

Both are implemented using binary search, so the elements must be sorted before calling.

bsearch

The bsearch function is the binary search implemented in the C standard library, defined in <stdlib.h>. In the C++ standard library, this function is defined in <cstdlib>. qsort and bsearch are the only two algorithmic functions in the C language.

Compared to qsort's four parameters (see Sorting-related STL), the bsearch function adds the parameter "address of the element to be searched" on the far left. The reason for passing it as an address is to facilitate the direct use of the same comparison function as qsort, enabling immediate search after sorting. Therefore, this parameter cannot be passed a specific value directly; instead, the value to be searched must first be stored in a variable, and then the address of that variable is passed.

Thus, the bsearch function has a total of five parameters: the address of the element to be searched, the array name, the number of elements, the size of each element, and the comparison rule. The comparison rule is still specified through a comparison function; see Sorting-related STL for details.

The return value of the bsearch function is the address of the found element, which is of type void*.

Note: bsearch differs from lower_bound and upper_bound mentioned above in two ways:

  • When there are multiple elements that meet the condition, it returns the first element that meets the condition during the binary search, which may be in the middle of multiple duplicate elements.
  • When the corresponding element cannot be found, it returns NULL.

lower_bound can achieve exactly the same functionality as bsearch, so any problem that can be solved using bsearch can also be solved by rewriting it with lower_bound. However, due to the second point mentioned above, for example, when searching for 3 in the sequence 1, 2, 4, 5, 6, implementing lower_bound's functionality with bsearch becomes difficult.

Is it impossible to implement lower_bound's functionality with bsearch? The answer is no; there are tricky techniques. By leveraging the compiler's handling of comparison functions: always pointing the first parameter to the element to be searched and the second parameter to an element in the array to be searched, bsearch can also be used to implement lower_bound and upper_bound, as shown in the example below. However, this requires the array to be searched to be a global array so that its starting address can be passed directly.

 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
int A[100005];  // Example global array

// Find the address of the first element not less than the element to be searched
int lower(const void *p1, const void *p2) {
  int *a = (int *)p1;
  int *b = (int *)p2;
  if ((b == A || compare(a, b - 1) > 0) && compare(a, b) > 0)
    return 1;
  else if (b != A && compare(a, b - 1) <= 0)
    return -1;  // Uses address subtraction, so the element type must be specified
  else
    return 0;
}

// Find the address of the first element greater than the element to be searched
int upper(const void *p1, const void *p2) {
  int *a = (int *)p1;
  int *b = (int *)p2;
  if ((b == A || compare(a, b - 1) >= 0) && compare(a, b) >= 0)
    return 1;
  else if (b != A && compare(a, b - 1) < 0)
    return -1;  // Uses address subtraction, so the element type must be specified
  else
    return 0;
}

Since few OI contestants write pure C nowadays and this method has limited utility, it is not a focus. For beginners, it is recommended to honestly use the lower_bound and upper_bound functions in C++.

Binary Answer

When solving problems, one often considers enumerating answers and then checking whether the enumerated value is correct. If monotonicity is satisfied, the conditions for using binary search are met. Replacing enumeration with binary search here becomes "binary answer."

Luogu P1873 Cutting Trees

Lumberjack Mirko needs to cut down \(M\) meters of wood. This is an easy job for Mirko because he has a beautiful new lumberjack machine that can cut down forests like wildfire. However, Mirko is only allowed to cut down a single row of trees.

Mirko's lumberjack machine works as follows: Mirko sets a height parameter \(H\) (meters), the machine raises a huge saw blade to height \(H\), and saws off all parts of the trees higher than \(H\) (of course, parts of trees not higher than \(H\) meters remain unchanged). Mirko then gets the parts of the trees that were sawn off.

For example, if the heights of a row of trees are \(20,~15,~10,~17\), and Mirko raises the saw blade to a height of \(15\) meters, the remaining heights of the trees after cutting will be \(15,~15,~10,~15\), and Mirko will get \(5\) meters of wood from the first tree and \(2\) meters from the fourth tree, totaling \(7\) meters of wood.

Mirko is very concerned about ecological protection, so he will not cut down too much wood. This is why he sets the saw blade as high as possible. Your task is to help Mirko find the largest integer height \(H\) for the saw blade such that he can get at least \(M\) meters of wood. That is, if the saw blade is raised by \(1\) meter more, he will not get \(M\) meters of wood.

Solution Idea

We can enumerate the answer from \(1\) to \(10^9\), but this naive approach will definitely not get full marks because enumerating from \(1\) to \(10^9\) takes too much time. We can perform binary search on the interval \([1,~10^9]\) as the answer and then check the feasibility of each answer (usually using a greedy method). This is binary answer.

Reference Code 
 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
29
int a[1000005];
int n, m;

bool check(int k) {  // Check feasibility, k is the saw blade height
  long long sum = 0;
  for (int i = 1; i <= n; i++)       // Check each tree
    if (a[i] > k)                    // If the tree is higher than the saw blade height
      sum += (long long)(a[i] - k);  // Accumulate the wood length
  return sum >= m;                   // If the minimum length is met, it is feasible
}

int find() {
  int l = 1, r = 1e9 + 1;   // Because it is left-closed and right-open, 10^9 needs to be incremented by 1
  while (l + 1 < r) {       // If the two points are not adjacent
    int mid = (l + r) / 2;  // Take the middle value
    if (check(mid))         // If feasible
      l = mid;              // Raise the saw blade height
    else
      r = mid;  // Otherwise lower the saw blade height
  }
  return l;  // Return the left value
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  cout << find();
  return 0;
}

After reading the above code, you will definitely have two questions:

  1. Why is the search interval left-closed and right-open?

    Because at the end of the search, it will be like this (taking the legal maximum as an example):

    Then it will be:

    The legal minimum is exactly the opposite.

  2. Why return the left value?

    Same as above.

Introduction

The bisection method can be used to approximate the zero of a function. To find the extremum point of a unimodal function, ternary search is usually required.

For a function \(f(x)\), if there exists \(x^*\) such that \(f(x)\) is monotonically increasing when \(x<x^*\) and monotonically decreasing when \(x>x^*\), then \(f(x)\) is called a unimodal function. Clearly, \(x^*\) is its maximum point, and \(f(x^*)\) is its maximum value.

Why not find the extremum point by finding the zero of the derivative?

Objectively, after finding the derivative, it is feasible to use the bisection method to find the zero of the derivative (since the function is unimodal, the zero of its derivative within the same range is unique) to obtain the extremum point of the unimodal function.

But first, for some functions, the process and result of finding the derivative are complex.

Second, in some problems, the unimodal function for which the extremum point needs to be found is not a single function but a function obtained by special operations on multiple functions (such as finding the maximum of the minimum values of multiple linear functions with incomplete monotonicity). In this case, the derivative function may be piecewise, and the function may be non-differentiable at certain points.

Note

Ternary search can find both the maximum of a unimodal function and the minimum of a "univalley function." For convenience, unless otherwise specified, the following discussion takes finding the maximum of a unimodal function as an example.

Process

The basic idea of ternary search is similar to binary search, but each operation requires selecting two points \(lmid < rmid\) (the two blue points in the figure below) within the current interval \([l,r]\) (between the two orange points in the figure below). As shown in the figure below, if \(f(lmid)<f(rmid)\), then in \([l,lmid)\) (the red part in the figure below), the function must be monotonically increasing, and the maximum point (the green point in the figure below) must not be in this interval, so this interval can be discarded; however, the possibility that the maximum point is to the right of \(rmid\) cannot be ruled out, so more intervals cannot be discarded. The converse is also true.

The correctness of ternary search does not depend on the choice of \(lmid\) and \(rmid\), and two trisection points are usually chosen. However, their choice does affect the efficiency of ternary search. This is because each operation of ternary search discards one of the two side intervals. To reduce the number of ternary search operations, the side intervals should be made as large as possible. Therefore, choosing \(lmid\) and \(rmid\) as \(mid-\varepsilon\) and \(mid+\varepsilon\) respectively for each operation is a good choice.

Implementation

Pseudocode is as follows:

\[ \begin{array}{l} \textbf{Algorithm}\operatorname{TernarySearch}(f,l,r):\\ \textbf{Input. } \text{A unimodal function } f(x) \text{ and its domain } [l,r]. \\ \textbf{Output. } \text{The maximizer }x^*\text{, up to an error of }\varepsilon\text{, and its value } f(x^*). \\ \textbf{Method. } \\ \begin{array}{ll} 1 & \textbf{while } r - l > \varepsilon\\ 2 & \qquad mid\gets (l+r)/2\\ 3 & \qquad lmid\gets mid - \varepsilon \\ 4 & \qquad rmid\gets mid + \varepsilon \\ 5 & \qquad \textbf{if } f(lmid) < f(rmid) \\ 6 & \qquad \qquad l\gets lmid \\ 7 & \qquad \textbf{else } \\ 8 & \qquad \qquad r\gets rmid \\ 9 & x^* \gets (l+r)/2 \\ 10& \textbf{return } x^*,~ f(x^*) \end{array} \end{array} \]
Integer Case

If the domain of the function \(f(x)\) is integers, then the above ternary search and the golden-section search described later should terminate when \(r-l\) is very small. For cases where \(r-l\) is small, the maximum point needs to be found by brute-force traversal.

If the cost of a single call to \(f(x)\) is high and the number of calls to \(f(x)\) needs to be further reduced, the constant factor of ternary search can be further improved using golden-section search. This is also an important part of the optimization method proposed by Hua Luogeng.

In ternary search, each iteration requires two function calls, and after a single iteration, the interval length is reduced to at most \(1/2\) of the original. This means that to achieve precision \(\varepsilon\), at least

\[ 2\log_2\dfrac{r-l}{\varepsilon} \]

function calls are required. This is the best result that ternary search can achieve. If other division points are chosen, such as trisection points, the number of calls will increase further because the interval shrinks more slowly after a single iteration.

The improvement idea of golden-section search is to reuse the division points calculated previously. In this way, except for the first iteration which requires two function calls, each subsequent iteration requires only one function call. Let the golden ratio be

\[ \phi = \dfrac{\sqrt{5}-1}{2} \approx 0.618. \]

During each iteration, the selected division points are the two golden-section points:

\[ m^l = \phi l +(1-\phi)r,~m^r = (1-\phi)l+\phi r. \]

The golden-section points divide the line segment with a self-similar structure. That is, \(m^l\) is the left golden-section point of the segment \([l,r]\) and also the right golden-section point of the segment \([l,m^r]\). The advantage of choosing division points in this way is that among the division points selected in the \(k>1\) iteration, there must be one division point that has been calculated before, and the previous result can be directly reused.

After choosing division points in this way, to achieve precision \(\varepsilon\), only

\[ 1 + \log_{\phi^{-1}}\dfrac{r-l}{\varepsilon} \approx 1 + 1.44\log_2\dfrac{r-l}{\varepsilon} \]

function calls are needed. Asymptotically, the number of function calls is fewer.

Pseudocode is as follows:

\[ \begin{array}{l} \textbf{Algorithm}\operatorname{GoldenSectionSearch}(f,l,r):\\ \textbf{Input. } \text{A unimodal function } f(x) \text{ and its domain } [l,r]. \\ \textbf{Output. } \text{The maximizer }x^*\text{, up to an error of }\varepsilon\text{, and its value } f(x^*). \\ \textbf{Method. } \\ \begin{array}{ll} 1 & lmid \gets \phi l + (1-\phi)r \\ 2 & rmid \gets (1-\phi)l + \phi r \\ 3 & lval \gets f(lmid) \\ 4 & rval \gets f(rmid) \\ 5 & \textbf{while } r - l > \varepsilon \\ 6 & \qquad \textbf{if } lval > rval \\ 7 & \qquad \qquad r \gets rmid \\ 8 & \qquad \qquad rmid \gets lmid \\ 9 & \qquad \qquad rval \gets lval \\ 10& \qquad \qquad lmid \gets \phi l + (1-\phi)r \\ 11& \qquad \qquad lval \gets f(lmid) \\ 12& \qquad \textbf{else} \\ 13& \qquad \qquad l \gets lmid \\ 14& \qquad \qquad lmid \gets rmid \\ 15& \qquad \qquad lval \gets rval \\ 16& \qquad \qquad rmid \gets (1-\phi)l + \phi r \\ 17& \qquad \qquad rval \gets f(rmid) \\ 18& x^* \gets (l+r)/2 \\ 19& \textbf{return }x^*,~f(x^*) \end{array} \end{array} \]

Example

Luogu P3382 - Ternary Search

Given an \(N\)-degree function and the range \([l, r]\), find the unique \(x\) such that the function is monotonically increasing on \([l, x]\) and monotonically decreasing on \([x, r]\).

Solution Idea

This problem requires finding the value of the independent variable when the \(N\)-degree function takes its maximum value on \([l, r]\). Clearly, ternary search can be used.

Reference Code 
 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
29
30
31
#include <cmath>
#include <iomanip>
#include <iostream>
using namespace std;

constexpr double eps = 1e-7;
int N;
double l, r, A[20], mid, lmid, rmid;

double f(double x) {
  double res = (double)0;
  for (int i = N; i >= 0; i--) res += A[i] * pow(x, i);
  return res;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> N >> l >> r;
  for (int i = N; i >= 0; i--) cin >> A[i];
  while (r - l > eps) {
    mid = (l + r) / 2;
    lmid = mid - eps;
    rmid = mid + eps;
    if (f(lmid) > f(rmid))
      r = mid;
    else
      l = mid;
  }
  cout << fixed << setprecision(6) << l;
  return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
eps = 1e-6
n, l, r = map(float, input().split())
a = tuple(map(float, input().split()))[::-1]


def f(x):
    return sum(x**i * j for i, j in enumerate(a))


while r - l > eps:
    mid = (l + r) / 2
    if f(mid - eps) > f(mid + eps):
        r = mid
    else:
        l = mid
print(round(l, 6))

Exercises

Fractional Programming

See: Fractional Programming

Fractional programming is usually described as the following problem: each item has two attributes \(c_i\) and \(d_i\), and the goal is to select some items in a certain way to maximize or minimize \(\frac{\sum{c_i}}{\sum{d_i}}\).

Classic examples include optimal ratio cycle, optimal ratio spanning tree, etc.

Fractional programming can be solved using binary search.

References

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用