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

See more blog posts.