Why it works
- The array is sorted, so one comparison with the middle shows which half can hold the target. The other half is thrown away whole.
- lo only moves past mid to the right and hi past mid to the left, so the range shrinks on every step and the loop always ends.
- The loop runs while lo <= hi, so a range of one number is still checked. When lo passes hi, no place is left where the target could be: it is not in the array.
Complexity
Time O(log n): every step halves the range, so 7 numbers take at most 3 checks. Memory O(1): three indices.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗