def lower_bound(array, first, last, value) # return first !< val in [first, last)
while first < last: # not empty
mid = first + (last - first)/2. # no overflow
if array[mid] < val : first = mid + 1
else: last = mid
return first. # or last
- No need to worry about onverflow:
mid = (2 * first + last – first) / 2 - +/- 1 only occurres one time
- Both first and last could be returned
Here is a clear explanation in Chinese: link