Binary Search

Easy#704find a number

You get an array of distinct numbers sorted in increasing order and a target number. Return the index of the target, or −1 if it is not in the array, in O(log n) time. Our example: [-4, 0, 3, 9, 14, 20, 27] and 15 — the answer is −1: 15 would stand between 14 and 20, but it is not there.

704 Binary SearchWalkthrough · 1×

Example: [-4, 0, 3, 9, 14, 20, 27], find 15. Faded numbers are thrown away: the target cannot be among them.

0-4102339414520627lo
still in the rangemiddle, checked nowthrown away

lo starts at the first index, 0

01/19
restart · back · play · step
Speed
1function search(nums, target):
2 lo = 0
3 hi = len(nums) - 1
4 while lo <= hi: // one number left still counts
5 mid = floor((lo + hi) / 2)
6 if nums[mid] == target:
7 return mid
8 if nums[mid] < target:
9 lo = mid + 1
10 else:
11 hi = mid - 1
12 return -1
state
lo
0
hi
–
mid
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The array is sorted, so one comparison with the middle shows which half can hold the target. The other half is thrown away whole.
  2. 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.
  3. 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 ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.