# 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?

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:

1. Scenario: find whether target in the range. Guess Number Higher or Lower
```class Solution(object):
def guessNumber(self, n):
"""
:type n: int
:rtype: int
"""
left, right = 1, n
while left <= right:
mid = int(left + (right-left)/2)
v = guess(mid)
if v == 0:
return mid
elif v == 1:
left = mid + 1
else:
right = mid - 1
return None
```

```class Solution(object):
"""
:type n: int
:rtype: int
"""
left, right = 1, n
while left < right:
mid = int(left + (right-left)/2)
right = mid
else:
left = mid + 1

# left == right
return left if isBadVersion(left) else None
```

The most impressive problems to me:

See all binarysearch problems: #binarysearch.

See more blog_posts.

Share It, If You Like It.