algorithms

(2024/1/16)when searching a sorted array using methods like binary search, it's not obvious about which index to return, should I return low, or "low + 1", or "high - 1", how to reason about the return value ?

Solution: see the comments of bisect_right() and bisect_left() in the following file:

https://github.com/OccupyMars2025/dengjunhui-data-structure-cpp-source-code/blob/main/src/Vector/bisect_from_python.py

while lo < hi:
    mid = (lo + hi) // 2
    if a[mid] < x:
        lo = mid + 1
    else:
        hi = mid

key point 1: after "a[mid] < x" branch is executed, we have a[lo - 1] < x , if this branch is never executed, then "lo" is never changed ; after "x <= a[mid]" branch is executed, we have x <= a[hi], if this branch is never executed, then "hi" is never changed

key point 2: when we exit the loop, we have hi = lo , hi = lo + 1, or similar things

key point 3: when we exit the loop, based on whether one branch has never been executed, we can get several situations

You can compare the analysis of correctness of binary search with that of interpolation search

https://github.com/OccupyMars2025/dengjunhui-data-structure-cpp-source-code/blob/main/src/Vector/Vector_search_interpolation.h

These two pieces of analysis show that: You don't have to "pretend" the algorithm is correct. In fact, just using some math, you can "rigorously prove" that the algorithm is correct. That's fantastic !

============