Algorithm dossier

  • Category: Search
  • Worst-case complexity: O(log n)
  • Approach: Divide & conquer
  • Data structure: Array
  • First formalised: 1940s

Why this snippet is Binary Search

Why binary search. Two pointers converge by halving. The midpoint compare picks which half to keep — < discards the left, > discards the right — so each iteration eliminates 50% of the remaining range. Pre-condition. a is *sorted*. The snippet doesn't enforce that — the caller must — but the algorithm only makes sense on a monotonic predicate (here, a[m] < t).

How to read a redacted algorithm

Algodle strips identifier names so the snippet has to be read for its shape: the control flow, the data structures it manipulates, the order in which it visits its input. Loops with two pointers crawling toward each other are usually search or partition. A recursion that splits its input in half and recurses on both halves is divide-and-conquer. A priority queue plus graph traversal is almost certainly Dijkstra, Prim, or A*. Six hint columns — category, complexity, approach, data structure, era — let you triangulate even when the snippet itself is opaque.