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 exa...
