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**

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

**Top Questions**

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: Tweet Counts Per Frequency
- 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: Majority Element II
- LeetCode: Longest Repeating Substring
- LeetCode: Longest Duplicate Substring
- LeetCode: Leftmost Column with at Least a One
- 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 Peak Element
- 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: Find First and Last Position of Element in Sorted Array
- LeetCode: Exam Room
- 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.