Find a value in a sorted list by repeatedly throwing away half of it.
I think of a number from 1 to 100. You guess 50. I say “higher”. Now you know it is in 51–100, so half the numbers are gone with one guess. Guess 75, “lower”… In about 7 guesses you always win. That is binary search: look at the middle, then discard the half that cannot contain the answer.
It only works if the list is sorted. Doubling the list size adds just one more step: 1,000,000 items need about 20 steps.
91 (the last item) and for 2 (the first). How many steps each?40, which is not in the list. What do lo and hi look like at the end?mid, move to mid+1 or mid-1, not mid, or you can loop forever.mid := lo + (hi-lo)/2, not (lo+hi)/2, which can overflow with huge indexes.