Binary search is important. The idea is simple.

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

Clarifications:

- Allow duplicate?
- What range you would choose to examine?
- 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

- Found. Target = 3. left == right, points to the value
- 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?
- Too small. Target = 1. [right(-1), left(0)]
- 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.

- Review: Binary Search Problems
- LintCode: Single Number IV
- LintCode: Leftmost One
- LintCode: Count Negative Number
- Leetcode: Valid Perfect Square
- Leetcode: Time Based Key-Value Store
- Leetcode: Sqrt(x)
- Leetcode: Single Element in a Sorted Array
- Leetcode: Search Insert Position
- Leetcode: Search in Rotated Sorted Array II
- Leetcode: Search in Rotated Sorted Array
- Leetcode: Search in a Sorted Array of Unknown Size
- Leetcode: Search for a Range
- Leetcode: Search a 2D Matrix II
- Leetcode: Search a 2D Matrix
- Leetcode: Preimage Size of Factorial Zeroes Function
- Leetcode: Most Profit Assigning Work
- Leetcode: Lowest Common Ancestor of a Binary Search Tree
- Leetcode: Longest Repeating Substring
- Leetcode: Guess Number Higher or Lower
- Leetcode: First Bad Version
- Leetcode: Find the Duplicate Number
- Leetcode: Find Smallest Letter Greater Than Target
- Leetcode: Find Minimum in Rotated Sorted Array II
- Leetcode: Find Minimum in Rotated Sorted Array
- Leetcode: Compare Strings by Frequency of the Smallest Character
- Leetcode: Closest Binary Search Tree Value
- Leetcode: Check If a Number Is Majority Element in a Sorted Array
- Leetcode: Binary Search
- Leetcode: Advantage Shuffle

See more blog_posts.

Share It, If You Like It.