Data-Structures-and-Algorithms

If you followed “Binary search isn’t about search” and “Binary search isn’t about search II” properly, the following statements should suffice as a summary: 1 2 L[0:l] < T < L[r:len(L)] # ordinary binary search loop invariant L[0:l] < T <= L[r:len(L)] # leftwise binary search loop invariant Let’s complete the triptych. Take a wild guess what invariant we use for rightmost element binary search: 1 L[0:l] <= T < L[r:len(L)] # rightwise binary search loop invariant A motivating example Consider again an array like...

In the first “Binary search isn’t about search” post, we spoke about using assert statements to enforce your loop invariants. Our plain old everyday binary search invariant can be summarized as such: For all x in L[0:l]1, x is strictly less than T, the element we are searching for. For all y in L[r:len(L)]2, y is strictly greater than T, the element we are searching for. Or, if we want to be even terser, we could note this as simply...

Suppose you’re trying to track down a bug that appeared in a series of Git commits. You’ve been idly keeping track of where this bug appears in your lucky commits by hand, while busy with other things. So far you’ve compiled this table: 1 2 3 4 5 6 7 8 9 10 0000000 🧼 clean, no bug. 0000001 🧼 0000002 🧼 0000003 🧼 0000004 🧼 0000005 🧼 0000006 🐛 bug first appears here....