Sannemo, Johan

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

Logic

• walks through pretty common syntax.

Sets and Sequences

• defines sets and sequences, and various notations.

Sums and Products

• introduces syntax, and declares a few closed forms without proofs.

Graphs

• defines various terms like vertices, edges, paths, walks, trails, trees, connectedness, edge-directionality, edge-weights, etc.

References

1. Principles of Algorithmic Problem Solving. Johan Sannemo. KTH Royal Institute of Technology. www.csc.kth.se . Oct 24, 2018.

(13 pages) defines computational problems, algorithms, programming languages, pseudo-code, and online judges.

1. Principles of Algorithmic Problem Solving. Johan Sannemo. KTH Royal Institute of Technology. www.csc.kth.se . Oct 24, 2018.