Given a sorted array and a target, return the index of the target, or minus 1 if it is missing. It must run in O of log n.
DSA Animator › DSA Revision › Binary Search › Binary Search
Remember: compare with the middle and throw away half. Use low plus high minus low over 2 to avoid overflow. The video solves Binary Search (LeetCode 704, Easy) with the Binary Search pattern from the Binary Search topic, and you can replay every step in the interactive Binary Search animation.
Given a sorted array and a target, return the index of the target, or minus 1 if it is missing. It must run in O of log n.
For minus 1, 0, 3, 5, 9, 12 and target 9, the answer is index 4.
Scanning from left to right is O of n. It ignores that the array is sorted.
Look at the middle element. If it is the target, you are done. If it is smaller, the target can only be on the right, so discard the left half. If it is bigger, discard the right half.
Low is 0 and high is 5, so mid is 2, which holds 3. 3 is smaller than 9, so low moves to 3. Now mid is 4, which holds 9. That is the target, so the answer is 4.
In code, loop while low is not past high. Compute mid as low plus half the distance to high, which avoids overflow. Return mid on a match, otherwise move low or high past mid. Each step halves the range, so it's O of log n time and O of 1 space.
Remember: compare with the middle and throw away half. Use low plus high minus low over 2 to avoid overflow.