Binary Search

This page briefly introduces binary search, ternary search derived from binary search, and binary search on the answer．

Binary Search

Definition

Binary search (also called half-interval search or logarithmic search) is an algorithm for finding an element in a sorted array．

Process

Consider finding a number in an ascending array．

Each time, binary search examines the middle element of the current part of the array. If the middle element is exactly the one being sought, the search ends. If the middle element is smaller than the target value, everything on its left is even smaller, so the target cannot be there and it is enough to search the right side. If the middle element is larger than the target, the same reasoning means that only the left side needs to be searched．

Properties

Time Complexity

The best-case time complexity of binary search is $O(1)$．

The average-case and worst-case time complexities of binary search are both $O(\log n)$. During the search, the algorithm halves the query interval each time, so an array of length $n$ requires at most $O(\log n)$ searches．

Space Complexity

The iterative version of binary search has space complexity $O(1)$．

The recursive version of binary search (without tail-call elimination) has space complexity $O(\log n)$．

Implementation

int binary_search(int start, int end, int key) {
  int ret = -1;  // Return index -1 if the data is not found
  int mid;
  while (start <= end) {
    mid = start + ((end - start) >> 1);  // A direct average may overflow, so use this formula
    if (arr[mid] < key)
      start = mid + 1;
    else if (arr[mid] > key)
      end = mid - 1;
    else {  // Check equality last because most searches satisfy either greater-than or less-than
      ret = mid;
      break;
    }
  }
  return ret;  // Single exit point
}

Minimize the Maximum

Note that “sorted” is used here in a generalized sense. If all elements on the left or all elements on the right side of an array satisfy some condition, while all elements on the other side do not, this can also be regarded as sorted (if satisfying the condition is represented by $1$ and not satisfying it by $0$, it is sorted in this dimension for the condition at hand)．In other words, binary search can be used to find the maximum (or minimum) value satisfying a condition．

To minimize the smallest possible value of the maximum satisfying a condition (minimize the maximum), the first idea is to enumerate the candidate “maximum” from small to large and then check whether it is valid. If the answer is monotonic, binary search can find it more quickly. Therefore, to solve this kind of “minimize the maximum” problem with binary search, the following three conditions must hold:

1. The answer lies in a fixed interval．
2. Finding a value that satisfies the condition may not be easy, but it must be relatively easy to determine whether a given value satisfies the condition．
3. The feasible solutions have a certain monotonicity over the interval. In other words, if $x$ satisfies the condition, then either $x + 1$ or $x - 1$ also satisfies it．(This gives the monotonicity mentioned above．)

Maximizing the minimum is analogous．

Binary Search in the STL

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

Both use binary search internally, so the elements must be sorted before they are called．

bsearch

The bsearch function is the C standard library's implementation of binary search and is defined in <stdlib.h>. In the C++ standard library, it is defined in <cstdlib>. qsort and bsearch are the only two algorithm-like functions in the C language．

Compared with the four parameters of qsort (STL related to sorting), the bsearch function adds the address of the element to be searched for at the far left. It is passed as an address so that the same comparison function as qsort can be reused directly, enabling an immediate search after sorting. Therefore, this parameter cannot be a value directly; the value to be searched for must first be stored in a variable, whose address is then passed．

Thus, bsearch has five parameters in total: the address of the element to be searched for, the array name, the number of elements, the element size, and the comparison rule. The comparison rule is still implemented by specifying a comparison function; see STL related to sorting for details．

The return value of bsearch is the address of the element found, and this address has type void．

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

• When multiple elements satisfy the condition, it returns the first such element encountered while performing the binary search, so this element may lie in the middle of the run of duplicate elements．
• When the corresponding element cannot be found, it returns NULL．

lower_bound can implement exactly the same functionality as bsearch, so a problem solved with bsearch can also be solved by rewriting it directly with lower_bound. However, because of the second difference above, implementing lower_bound with bsearch is difficult in cases such as searching for 3 in the sequence 1, 2, 4, 5, 6．

Is it necessarily impossible to implement lower_bound with bsearch? No; there is a rather tricky technique. Taking advantage of the compiler's handling of the comparison function—its first parameter always points to the element being searched for, while its second parameter points to an element in the array being searched—we can also implement lower_bound and upper_bound with bsearch, as shown below. The searched array must be global so that its first address can be passed directly．

int A[100005];  // Example global array

// Find the address of the first element not less than the element being searched for
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;  // Address subtraction is used, so the element type must be specified
  else
    return 0;
}

// Find the address of the first element greater than the element being searched for
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;  // Address subtraction is used, so the element type must be specified
  else
    return 0;
}

Few OI contestants now write pure C, and this method has limited usefulness, so it is not a focus here. Beginners are advised to simply use the C++ lower_bound and upper_bound functions．

Binary Search on the Answer

When solving a problem, one often considers enumerating an answer and then checking whether the enumerated value is correct. If the condition is monotonic, the requirements for binary search are met. Replacing this enumeration with binary search gives “binary search on the answer”．

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 every tree
    if (a[i] > k)                    // If the tree is taller than the blade
      sum += (long long)(a[i] - k);  // Accumulate the amount of wood
  return sum >= m;                   // Meeting the minimum length means it is feasible
}

int find() {
  int l = 1, r = 1e9 + 1;   // The interval is left-closed and right-open, so add 1 to 10^9
  while (l + 1 < r) {       // While the two points are not adjacent
    int mid = (l + r) / 2;  // Take the midpoint
    if (check(mid))         // If feasible
      l = mid;              // Raise the blade height
    else
      r = mid;  // Otherwise lower the 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;
}

Ternary Search

Introduction

Binary search can be used to approximately find a zero of a function. If the extremum of a unimodal function is needed, ternary search is usually used．

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

Process

The basic idea of ternary search is similar to that of binary search, but each operation chooses two points within the current interval $[l,r]$, with $lmid < rmid$ (between the two orange points in the figure below; the two blue points in the figure). As shown below, if $f(lmid)<f(rmid)$, then the function must be monotonically increasing on $[l,lmid)$ (the red part below), so the maximizer (the green point below) cannot lie in this interval and it can be discarded. However, we cannot rule out the possibility that the maximizer is to the right of $rmid$, so no more of the interval can be discarded. The converse is analogous．

The correctness of ternary search does not depend on the choice of $lmid$ and $rmid$; usually, the two trisection points can be used. However, their choice does affect the efficiency of ternary search. Each operation discards one of the two side intervals. To reduce the number of operations, the two side intervals should be as large as possible. Therefore, choosing $lmid$ and $rmid$ as $mid-\varepsilon$ and $mid+\varepsilon$, respectively, at each operation is a good choice. In fact, choosing $mid\pm \varepsilon$ amounts to calculating, at $mid$, the approximate derivative $\dfrac{f(mid+\varepsilon)-f(mid-\varepsilon)}{2\varepsilon}$ and determining on which side of $mid$ the extremum lies from its sign．

Implementation

The pseudocode is as follows:

Optimization: Golden-Section Search

If a single call to $f(x)$ is expensive, the constant factor of ternary search can be improved further with golden-section search, reducing the number of calls to $f(x)$. 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 one iteration the interval length is reduced to at most $1/2$ of its original length. This means that reaching precision $\varepsilon$ requires at least

function calls. This is the best result ternary search can achieve. If other division points are chosen, such as trisection points, the number of calls increases because the interval shrinks more slowly after each iteration．

The idea behind golden-section search is to reuse division points calculated earlier. Thus, apart from the first iteration, which requires two function calls, all subsequent iterations require only one function call. Let the golden ratio for division be

At each iteration, choose the two golden-section points:

The points dividing a segment in the golden ratio have a self-similar structure. In other words, $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 the points this way is that among the points selected in iteration $k>1$, one is guaranteed to have already been evaluated and its result can be reused directly．

With these division points, reaching precision $\varepsilon$ requires only

function calls. In the asymptotic sense, fewer function calls are needed．

The pseudocode is as follows:

Example Problems

#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;
}

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

• UVa 1476 - Error Curves
• UVa 10385 - Duathlon
• UOJ 162 -【Tsinghua Training Camp 2015】Light Bulb Test
• Luogu P7579 - “RdOI R2” Weighing (weigh)

Fractional Programming

See: Fractional programming

Fractional programming usually refers to the following problem: each item has two attributes $c_i$ and $d_i$, and we must select several items in some way so that $\frac{\sum{c_i}}{\sum{d_i}}$ is maximized or minimized．

Classic examples include the maximum-ratio cycle and the maximum-ratio spanning tree．

Fractional programming can be solved with binary search．

References

• Ternary search - Wikipedia
• Golden-section search - Wikipedia
• Ternary search - CP Algortihms