Group 1: The Core Binary Search Pattern
This group introduces the fundamental binary search algorithm. These problems are direct applications of the classic template, where you search for a target value within a sorted array. Mastering this template is the first and most critical step.
| # | Problem | Link | Concept | Description of Difficulty Increase | ✓ |
|---|---|---|---|---|---|
| 1 | Binary Search | Link | Core Template | Base case. The quintessential binary search problem. It establishes the core template of `left`, `right`, and `mid` pointers. | |
| 2 | Search Insert Position | Link | Core Template (Variation) | A slight variation of the base case. Instead of returning -1, you return the index where the target *should* be, which is a natural outcome of the `left` pointer's final position. | |
| 3 | Guess Number Higher or Lower | Link | Abstract Search Space | Introduces binary search on an abstract concept (a range of numbers) rather than a concrete array, using an API to guide the search. | |
| 4 | First Bad Version | Link | Finding the First 'True' | A classic application of binary search to find the first occurrence of a condition (the first bad version). This pattern is crucial for many harder problems. |
Group 2: Binary Search on the Answer
This group introduces a key conceptual leap: applying binary search not on the input array, but on the range of possible answers. These problems ask “what is the optimal value?”, and you binary search for that value.
| # | Problem | Link | Concept | Description of Difficulty Increase | ✓ |
|---|---|---|---|---|---|
| 5 | Sqrt(x) | Link | Search on Answer | Base case for this pattern. Instead of searching an array, you search for the correct integer answer in the range `[0, x]`. | |
| 6 | Valid Perfect Square | Link | Search on Answer | Boring variation. Nearly identical to `Sqrt(x)`, reinforcing the concept of searching for a numerical answer. | |
| 7 | Arranging Coins | Link | Search on Answer (Math) | The condition to check (`k * (k+1) / 2 <= n`) is a mathematical formula, showing that the 'check' function can be anything. | |
| 8 | Special Array With X Elements Greater Than or Equal to X | Link | Search on Answer | A more complex 'check' function. You binary search for the answer `x` and then count elements in the array to validate it. |
Group 3: Binary Search on Variations of Sorted Arrays
This group applies the binary search pattern to arrays that are sorted but have a twist, or where the goal is slightly different from finding a specific target.
| # | Problem | Link | Concept | Description of Difficulty Increase | ✓ |
|---|---|---|---|---|---|
| 9 | Peak Index in a Mountain Array | Link | Property-Based Search | Instead of a target value, you search for a property of the element (`arr[i] > arr[i+1]`), using the monotonic nature of the slopes. | |
| 10 | Find Smallest Letter Greater Than Target | Link | Upper Bound Search | A variation on finding an element, this asks for the 'upper bound' or the next element if the target isn't found, handling wrap-around logic. | |
| 11 | Kth Missing Positive Number | Link | Search on Missing Count | A clever application where you binary search for the location where the `k`-th missing number would be, based on the number of missing elements at each index. | |
| 12 | Find Target Indices After Sorting Array | Link | Search after Sorting | Combines sorting with binary search. The core idea is to first sort, then find the start and end of the target elements. |
Group 4: Binary Search as a Tool with Other Techniques
In this group, binary search is used as an efficient tool to search through sorted data, often in combination with another technique or as a major optimization over a brute-force approach.
| # | Problem | Link | Concept | Description of Difficulty Increase | ✓ |
|---|---|---|---|---|---|
| 13 | Two Sum II - Input Array Is Sorted | Link | Binary Search for Complement | While optimally solved with two pointers, it can be solved by iterating through the array and using binary search to find the complement for each element. | |
| 14 | Intersection of Two Arrays | Link | Search after Sorting | A common strategy: sort one array, then iterate through the second array, using binary search to efficiently check for existence in the first. | |
| 15 | Intersection of Two Arrays II | Link | Search after Sorting | Boring variation. Similar to the previous problem but handles duplicates, often solved with two pointers but binary search is a valid approach. | |
| 16 | Check If N and Its Double Exist | Link | Search after Sorting | After sorting, you can iterate through the array and binary search for `2*x`, which is more efficient than a nested loop. | |
| 17 | Fair Candy Swap | Link | Search for Calculated Target | Requires calculating the target value each person needs. After sorting one array, you can iterate through the other and binary search for the required candy size. | |
| 18 | Count Negative Numbers in a Sorted Matrix | Link | Binary Search on Each Row | Applies binary search to each row of a matrix to find the first negative number, leveraging the sorted property of each row. | |
| 19 | The K Weakest Rows in a Matrix | Link | Binary Search for Count | A clever use-case where binary search can quickly find the number of soldiers (1s) in each row, which is then used for sorting. | |
| 20 | Find the Distance Value Between Two Arrays | Link | Search for Range | After sorting one array, you can use binary search to efficiently check if any element within the distance `d` exists for each element of the other array. |