Interview Concept: Lower Bound vs Upper Bound Binary Search
Lower bound vs upper bound binary search explained: first index >= target vs first index > target, with ready templates in Python, Java and C++.
-
Arrays
- Find the Largest Element in an Array
- Find the Second Largest Element in an Array
- Reverse an Array In Place
- Check if an Array Is Sorted
- Remove Duplicates from a Sorted Array
- Move Zeroes to the End of an Array
- Rotate an Array by K Positions
- Two Sum
- Maximum Subarray Sum (Kadane's Algorithm)
- Best Time to Buy and Sell Stock
- Sort an Array of 0s, 1s and 2s (Dutch National Flag)
- Find the Missing Number in an Array
- Find the Duplicate Number in an Array
- Union of Two Sorted Arrays
- Intersection of Two Sorted Arrays
- Prefix Sum Array and Range Sum Queries
- Majority Element (Boyer-Moore Voting Algorithm)
- Merge Overlapping Intervals
- Next Permutation
- Product of Array Except Self
- Subarray Sum Equals K
- Merge Two Sorted Arrays In Place
- Maximum Product Subarray
- 3Sum: Find All Triplets That Sum to Zero
- Trapping Rain Water
- Container With Most Water
- Rotate Image (Matrix 90 Degree Rotation)
- Spiral Matrix Traversal
- Set Matrix Zeroes
- Kth Largest Element in an Array (Quickselect)
-
Strings
- Reverse a String In Place
- Check if a String Is a Palindrome
- Check if Two Strings Are Anagrams
- Count Frequency of Characters in a String
- First Non-Repeating Character in a String
- Reverse Words in a Sentence
- Check if a String Contains Only Digits
- Remove Duplicate Characters from a String
- Longest Substring Without Repeating Characters
- Group Anagrams
- Valid Parentheses
- String to Integer (atoi)
- Longest Common Prefix
- Implement strStr() - Naive Pattern Matching
- Run-Length Encoding of a String
- Check if a String Is a Rotation of Another
- Longest Palindromic Substring
- Minimum Window Substring
- Zigzag Conversion
- KMP Pattern Matching Algorithm
- Rabin-Karp Pattern Matching Algorithm
- Z-Algorithm for Pattern Matching
- Longest Palindromic Subsequence
- Edit Distance Between Two Strings
- Word Break Problem
- Decode Ways
- String Compression (In-Place)
- Count and Say
- Roman to Integer
- Integer to Roman
- Valid Palindrome II (At Most One Deletion)
- Longest Repeating Character Replacement
- Multiply Two Numbers Represented as Strings
- Why Strings Are Immutable (Interview Concept)
- Time Complexity of Common String Operations (Interview Co...
-
Sliding Window
- Maximum Sum Subarray of Size K (Fixed Window)
- Average of All Subarrays of Size K
- Maximum Number of Vowels in a Substring of Length K
- First Negative Integer in Every Window of Size K
- K Radius Subarray Averages
- Max Consecutive Ones
- Max Consecutive Ones III (At Most K Flips)
- Longest Subarray With Sum At Most K
- Minimum Size Subarray Sum
- Fruit Into Baskets (Longest Subarray With At Most 2 Disti...
- Longest Subarray With At Most K Distinct Elements
- Subarray Product Less Than K
- Maximum Average Subarray I
- Sliding Window Maximum (Monotonic Deque)
- Find All Anagrams in a String (Sliding Window)
- Repeated DNA Sequences (Fixed Window Hashing)
- Longest Turbulent Subarray
- Maximum Erasure Value (Longest Unique Subarray Sum)
- Longest Continuous Increasing Subsequence
- Grumpy Bookstore Owner
- Maximum Points You Can Obtain from Cards
- Binary Subarrays With Sum (Exactly K Trick)
- Count Number of Nice Subarrays (Exactly K Odd Numbers)
- Continuous Subarray Sum (Multiple of K)
- Minimum Operations to Reduce X to Zero
- Maximum Frequency After K Increments
- Sliding Window Median
- Substring With Concatenation of All Words
- Count Complete Subarrays in an Array
- Number of Subarrays With Bounded Maximum
- Maximum Sum of Distinct Subarrays With Length K
- Shortest Subarray With Sum At Least K (With Negatives)
- Fixed-Size vs Variable-Size Sliding Window (Interview Con...
- When to Use Sliding Window vs Two Pointers (Interview Con...
- Recognizing a Sliding Window Problem (Interview Concept)
-
Two Pointers
- Two Sum II - Input Array Is Sorted
- Valid Palindrome (Two Pointer Check)
- Reverse Vowels of a String
- Remove Element In Place
- Move Zeroes Using Two Pointers
- 3Sum Closest
- 4Sum
- Sort Array By Parity
- Squares of a Sorted Array
- Merge Two Sorted Arrays (Two Pointer)
- Intersection of Two Arrays II
- Backspace String Compare
- Trapping Rain Water (Two Pointer Approach)
- Container With Most Water (Two Pointer Approach)
- Partition Labels
- Sort Colors (Dutch National Flag Two Pointer)
- Remove Duplicates from Sorted Array II
- Linked List Cycle Detection (Fast and Slow Pointers)
- Middle of the Linked List
- Palindrome Linked List Check
- Boats to Save People
- Valid Triangle Number
- Minimum Number of Swaps to Make Sequences Increasing
- Sentence Similarity Using Two Pointers
- Shortest Distance to a Character
- Interleaving String Check
- DNA Complement Matching
- Is Subsequence Check (Two Pointer)
- Interview Concept: Same Direction vs Opposite Direction Two Pointers
- Interview Concept: Fast and Slow Pointer Technique Explained
-
Searching & Binary Search
- Binary Search (Classic Iterative)
- Binary Search (Recursive)
- Search Insert Position
- First and Last Position of Element in Sorted Array
- Search in Rotated Sorted Array
- Search in Rotated Sorted Array II (With Duplicates)
- Find Minimum in Rotated Sorted Array
- Find Peak Element
- Sqrt(x) Using Binary Search
- Koko Eating Bananas
- Capacity To Ship Packages Within D Days
- Split Array Largest Sum
- Median of Two Sorted Arrays
- Search a 2D Matrix
- Search a 2D Matrix II
- Find K Closest Elements
- Kth Smallest Element in a Sorted Matrix
- Aggressive Cows (Binary Search on Answer)
- Allocate Minimum Number of Pages
- Single Element in a Sorted Array
- Find the Smallest Divisor Given a Threshold
- Binary Search on a Function (Ternary Search Alternative)
- Count of Smaller Numbers After Self
- Time Based Key-Value Store
- Guess Number Higher or Lower
- H-Index II
- Find Right Interval
- Random Pick with Weight
- Interview Concept: Lower Bound vs Upper Bound Binary Search
- Interview Concept: Binary Search on Answer Pattern Explained
-
Sorting
- Bubble Sort Implementation
- Selection Sort Implementation
- Insertion Sort Implementation
- Merge Sort Implementation
- Quick Sort Implementation
- Heap Sort Implementation
- Counting Sort Implementation
- Radix Sort Implementation
- Bucket Sort Implementation
- Sort an Array (Built-in vs Custom Comparator)
- Merge Intervals Using Sorting
- Largest Number Formed from an Array
- Custom Sort String
- Sort Characters By Frequency
- Kth Largest Element (Sorting Approach)
- Relative Sort Array
- Wiggle Sort
- Wiggle Sort II
- H-Index (Sorting Approach)
- Meeting Rooms (Can Attend All Meetings)
Overview
Most binary-search bugs come from fuzzy boundaries. Two precise templates remove the guesswork: lower bound (first index whose value is >= target) and upper bound (first index whose value is > target). Learn these two and most variants fall out.
Lower Bound (first value >= target)
Python
def lower_bound(nums, target):
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < target:
lo = mid + 1
else:
hi = mid
return loJava
int lowerBound(int[] nums, int target) {
int lo = 0, hi = nums.length;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}C++
int lowerBound(vector<int>& nums, int target) {
int lo = 0, hi = (int)nums.size();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo; // same as std::lower_bound
}Upper Bound (first value > target)
Python
def upper_bound(nums, target):
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] <= target:
lo = mid + 1
else:
hi = mid
return loJava
int upperBound(int[] nums, int target) {
int lo = 0, hi = nums.length;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] <= target) lo = mid + 1;
else hi = mid;
}
return lo;
}C++
int upperBound(vector<int>& nums, int target) {
int lo = 0, hi = (int)nums.size();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] <= target) lo = mid + 1;
else hi = mid;
}
return lo; // same as std::upper_bound
}What You Can Build From Them
- Count of a value = upper_bound - lower_bound.
- First/last position = lower_bound(target) and upper_bound(target) - 1.
- Exists? check
i = lower_bound; i < n and nums[i] == target. - The only difference between the two templates is
<versus<=.
Key Takeaways
- Use the half-open window
[lo, hi)withhi = nto avoid off-by-one bugs. - Lower bound uses
nums[mid] < target; upper bound usesnums[mid] <= target. - Reference: C++
std::lower_bound/std::upper_bound; Pythonbisect_left/bisect_right.