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. 0000007 🐛 0000008 🐛 0000009 🤔 bug mysteriously disappears... Then an EMP explodes in your vicinity and scrambles your memory circuits. The Internet is down, you don’t have the git-bisect man pages downloaded locally, and all you remember is that your first commit was good, your last commit was good but for reasons you don’t understand, and something bad is probably still lurking in there. But where? ...