Look at the middle element, decide which half can still contain the answer, and repeat. 1000 items need at most about 10 steps. git bisect applies it to commit history.