Developers

Binary Search

EasyBinary searchAlso known as LeetCode 704

You get a list of integers sorted from smallest to largest, with no repeated values, and a target value.

Return the position (starting from 0) where the target sits in the list, or -1 if the list does not contain it. Aim for time that grows with log n, not n.

Examples

Input nums = [-1, 0, 3, 5, 9, 12], target = 9
Output 4
Input nums = [-1, 0, 3, 5, 9, 12], target = 2
Output -1
2 is not in the list.
Input nums = [5], target = 5
Output 0

Constraints

  • 1 <= nums.length <= 100,000
  • -1,000,000 <= nums[i], target <= 1,000,000
  • nums is sorted in increasing order and has no repeated values

Stuck? Take one hint at a time

Common mistakes
  • Writing the loop as lo < hi, which skips the last remaining position and misses the target when it is the last position left.
  • Setting lo = mid or hi = mid instead of mid + 1 or mid - 1, which can loop forever when the window has two positions.
  • Computing mid as (lo + hi) / 2 in a language with fixed size integers. It overflows only for lists of about a billion entries, but lo + (hi - lo) / 2 costs nothing.
  • Returning mid + 1, or the value, instead of the position.
Questions an interviewer may ask next
  • The list may contain repeated values. Return the position of the first occurrence. (Keep searching left after a match.)
  • Return the position where the target would be inserted to keep the list sorted. (The same loop, returning lo.)
  • The list is sorted but was rotated at an unknown point. (Search in Rotated Sorted Array.)
  • You are not given the length of the list, only a way to read position i. (Grow the window by doubling first.)