Review: Binary Search Problems

Binary search is important. The idea is simple.

But you wouldn’t believe how incredibly useful it would be.



Clarifications:

  1. Allow duplicate?
  2. What range you would choose to examine?
  3. How you can reduce the dataset into half?

Ideas

Name Example
Break case for left+1<right: the same or adjacent
Break case for left<right
Break case for left<=right

Where Left/Right Would Be After Search?
l = [2, 3, 8, 12, 20, 35], target = 4

  1. Found. Target = 3. left == right, points to the value
  2. In the middle. Target = 11. [right, Target, left]. The previous step would be right==left, and the value is smaller than the target. Do you know why?
  3. Too small. Target = 1. [right(-1), left(0)]
  4. Too big. Target = 36. [right(len-1), left(len)]

Scenarios:

Name Example
Find whether target in the range Guess Number Higher or Lower
Find the first target First Bad Version
Find smallest letter greater than target Find Smallest Letter Greater Than Target
Search insert position  

The most impressive problems to me:

See all binarysearch problems: #binarysearch.

See more blog_posts.

linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.