I read a conference paper lately that has a pseudo code. In the code, there was a binary search and I noticed that the algorithm does not stop. That part in the paper is not very important but I myself confused at first, so I make it clear.
I took a look at Knuth's TAOCP and I translated the description into Python:
# search key between [l,u] # returns -1 on failure def search1(key, arr): l = 0 u = len(arr)-1 while l<=u: m = (l+u)/2 if arr[m] == key: return m elif arr[m] > key: u = m-1 else: l = m+1 return -1
This is simple and it has the case for failure.
What happens if the upper limit is an open end? I re-wrote it in this way.
# search key between [l,u) # you need to be sure that you have an answer in arr def search2(key,arr): l = 0 u = len(arr) while l+1<u: m = (l+u)/2 if arr[m] > key: u = m else: l = m return l
It does not have the case for failure so you need to be careful when you call it. There is a trick to compare l and u this case.
The algorithm in the paper is a mix of these and it does not stop.