Binary search is important. The idea is simple.

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

**Basic Abstractions**

Name | Summary |
---|---|

What are the arrays to be examined? | |

How to divide them into half? | |

Check the middle and how to drop one half? |

**Code Skeleton**

**Questions**

Name | Example |
---|---|

Clarifications: whether array is sorted? | |

Clarifications: whether array allow duplicates? | |

How to initialize? | left, right := 0, len(l)-1 VS left, right := 0, len(l) |

How to check, drop? | target -> middle vs middle -> target |

How to move? | left = mid, left = mid+1, left = mid-1 |

When to break? | left<right: adjacent, left<=right: overlap |

What break means? | |

Any corner case? |

**Scenarios**

Name | Example |
---|---|

Find whether target in the range | Leetcode: Guess Number Higher or Lower |

Find the first target with duplicates | Leetcode: First Bad Version |

Find the last target with duplicates | |

Search insert position | Leetcode: Search Insert Position |

Find smallest letter greater than target | Leetcode: Find Smallest Letter Greater Than Target |

Leecode: Find Right Interval | |

Leecode: Search for a Range | |

Leecode: Sqrt(x) |

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: Remove Interval
- Leetcode: Random Point in Non-overlapping Rectangles
- Leetcode: Random Pick with Weight
- Leetcode: Preimage Size of Factorial Zeroes Function
- Leetcode: Peak Index in a Mountain Array
- Leetcode: Online Election
- Leetcode: Most Profit Assigning Work
- Leetcode: Missing Element in Sorted Array
- Leetcode: Minimize Max Distance to Gas Station
- Leetcode: Maximum Width Ramp
- Leetcode: Maximum Profit in Job Scheduling
- Leetcode: Maximum Average Subarray II
- Leetcode: Longest Repeating Substring
- Leetcode: Longest Duplicate Substring
- Leetcode: Kth Smallest Number in Multiplication Table
- Leetcode: Koko Eating Bananas
- Leetcode: K-th Smallest Prime Fraction
- Leetcode: H-Index II
- 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: Find K-th Smallest Pair Distance
- Leetcode: Find in Mountain 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: Capacity To Ship Packages Within D Days
- Leetcode: Binary Search
- Leetcode: Advantage Shuffle

See more blog_posts.