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. [display-posts tag=”binarysearch” posts_per_page=”100” orderby=”title”]
See more blog_posts.
