I went through this code given in [Topcoder binary search tutorial](http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch).

```
binary_search(lo, hi, p):
    while lo < hi:
        mid = lo + (hi-lo)/2
        if p(mid) == true:
            hi = mid
        else:
            lo = mid+1

    if p(lo) == false:
        complain                // p(x) is false for all x in S!

    return lo                   // lo is the least x for which p(x) is true

```

I am not able to reason as to why always low is going to point to what we want i.e. lo is the least x for which p(x) is true ?

I have tried this on examples and this comes out to be true but I am not able to think about it logically.

Some sort of proof using some invariant which is maintained in the loop will be helpful .

Thanks.