Binary-Search

Binary Search on a Non-Decreasing \(f: \mathbb{R} \to \mathbb{R}\)

Given a number \(L\) and a non-decreasing function \(f: \mathbb{R} \to \mathbb{R}\), find the greatest \(x\) such that \(f(x) \le L\). To start, there are two numbers \(lo\) and \(hi\), such that \(f(lo) \le L < f(hi)\).

Algorithm

double binary_search(double lo, double hi, double lim) {
  while (hi - lo > precision) {
    const double mid = (hi + lo) / 2;
    if (lim < f(mid)) hi = mid; // Search in left half
    else lo = mid; // Search in right half
  }
  return lo;
}

Problem Description

Given a 1-indexed array of integers that is sorted in non-decreasing order, find two numbers such that they add up to a target number.

Solution: Linear Scan with Binary Search

#binary-search

At its core, the problem is a binary search one. Given \(a\), find \(b = t - a\) in the right side of array. If \(a > \lfloor t / 2 \rfloor\), then there is no possible \(b\) to the right because \(b \ge a\) and \(2a > t\).