MIND WARP

my binary search does not actually return the index of the desired item in the list or negative one.

it returns

"this is where x should go if it were in this list."

as in like

If x=3, then p=1 is returned.
if x= -2, then p = -1 is returned
If x = 7, then p = 3 is returned.

WHAT KIND OF BINARY SEARCH IS THIS.

So then I'm thinking...

if something were smaller than all the elements in the list, wouldn't the index where it should go be 0 ?
because if we're using the logic that something smaller than all the elements in the list gets -1, then shouldn't something bigger than all the elements in the list get n, not n-1?

but then I go look at the actual stipulations of the post condition, namely A[0...p] <= x < A[p+1 ... n-1],

and then I work through the examples in my head, and I understand.

Now I need to redo my algorithm :(.
At least the loop invariant proof will remain unchanged.