[EN] Divide, Conquer and Binary Search
Problem Suppose we have two arrays a[1], a[2], ..., a[n] and b[1], b[2], ..., b[m] , and a predicate P(a, b) . For each index i (1 ≤ i ≤ n) we want to find the least j (1 ≤ j ≤ m) such that P(a[i], b[j]) is true. Naive Solution With the information we have, we can't do much. The optimal solution given what we know so far is: Iterate over every i, then over every j, until we find a match. fn search(i) { solution[i] = m+ 1 for j in 1 . .m { if P( a [i], b [j]) { solution[i] = j break } } } for i in 1 . .n { search(i) } This is O(n * m). Additional constraints Let's introduce a construct that will lead to a faster solution. Consider this definition: P'(a, B) = { true if there is some b in B such that P(a, b) { false otherwise Let's say we can evaluate P' in O(1), given some O(|B|) precomputation. Then, an alternative strategy becomes available. Solution For each i, use bi