Binary Search Variations
Finding ranges, boundaries, first/last occurrences, and searching in rotated arrays. Advanced binary search applications.
The basic binary search finds an exact match. But what about finding the first occurrence, the last occurrence, or the insertion point? These variations are essential for solving real-world problems.
Lower Bound: First Position >= Target
Find the first position where we could insert the target while keeping the array sorted.
fn lower_bound(arr: &[i32], target: i32) -> usize {
// Find first position where arr[i] >= target
let mut left = 0;
let mut right = arr.len();
while left < right {
let mid = left + (right - left) / 2;
if arr[mid] < target {
left = mid + 1;
} else {
right = mid;
}
}
left
}
fn main() {
let arr = vec![1, 2, 4, 4, 4, 5, 6];
println!("{}", lower_bound(&arr, 4)); // 2 (first 4)
println!("{}", lower_bound(&arr, 3)); // 2 (where 3 would go)
println!("{}", lower_bound(&arr, 7)); // 7 (past end)
}
Finding lower_bound of 4 in [1, 2, 4, 4, 4, 5, 6]:
Step 1: mid = 3, arr[3] = 4 >= 4, right = 3
[1, 2, 4, 4, 4, 5, 6]
↑
Step 2: mid = 1, arr[1] = 2 < 4, left = 2
[1, 2, 4, 4, 4, 5, 6]
↑
Step 3: mid = 2, arr[2] = 4 >= 4, right = 2
[1, 2, 4, 4, 4, 5, 6]
↑
left == right == 2 → return 2
Upper Bound: First Position > Target
Find the first position where the element is strictly greater than target.
fn upper_bound(arr: &[i32], target: i32) -> usize {
// Find first position where arr[i] > target
let mut left = 0;
let mut right = arr.len();
while left < right {
let mid = left + (right - left) / 2;
if arr[mid] <= target {
left = mid + 1;
} else {
right = mid;
}
}
left
}
fn main() {
let arr = vec![1, 2, 4, 4, 4, 5, 6];
println!("{}", upper_bound(&arr, 4)); // 5 (first position after all 4s)
println!("{}", upper_bound(&arr, 3)); // 2
println!("{}", upper_bound(&arr, 7)); // 7
}
Lower vs Upper Bound
Lower bound: first position >= target. Upper bound: first position > target. The difference is in the condition: < vs <=. Together, they define the range of equal elements.
Find First and Last Occurrence
Using lower and upper bounds to find the range of a target:
fn search_range(arr: &[i32], target: i32) -> Vec<i32> {
// Find [first, last] indices of target
let first = lower_bound(arr, target);
// Check if target exists
if first == arr.len() || arr[first] != target {
return vec![-1, -1];
}
// Last occurrence is one before upper bound
let last = upper_bound(arr, target) - 1;
vec![first as i32, last as i32]
}
fn lower_bound(arr: &[i32], target: i32) -> usize {
let mut left = 0;
let mut right = arr.len();
while left < right {
let mid = left + (right - left) / 2;
if arr[mid] < target {
left = mid + 1;
} else {
right = mid;
}
}
left
}
fn upper_bound(arr: &[i32], target: i32) -> usize {
let mut left = 0;
let mut right = arr.len();
while left < right {
let mid = left + (right - left) / 2;
if arr[mid] <= target {
left = mid + 1;
} else {
right = mid;
}
}
left
}
fn main() {
let arr = vec![5, 7, 7, 8, 8, 8, 10];
println!("{:?}", search_range(&arr, 8)); // [3, 5]
println!("{:?}", search_range(&arr, 6)); // [-1, -1]
}
Count Occurrences
fn count_occurrences(arr: &[i32], target: i32) -> usize {
// Count how many times target appears
let first = lower_bound(arr, target);
let last = upper_bound(arr, target);
last - first
}
fn lower_bound(arr: &[i32], target: i32) -> usize {
let mut left = 0;
let mut right = arr.len();
while left < right {
let mid = left + (right - left) / 2;
if arr[mid] < target {
left = mid + 1;
} else {
right = mid;
}
}
left
}
fn upper_bound(arr: &[i32], target: i32) -> usize {
let mut left = 0;
let mut right = arr.len();
while left < right {
let mid = left + (right - left) / 2;
if arr[mid] <= target {
left = mid + 1;
} else {
right = mid;
}
}
left
}
fn main() {
let arr = vec![1, 2, 2, 2, 3, 4, 4];
println!("{}", count_occurrences(&arr, 2)); // 3
println!("{}", count_occurrences(&arr, 5)); // 0
}
Find Insertion Position
fn find_insertion_position(arr: &[i32], target: i32) -> usize {
// Where should target be inserted to maintain sorted order?
lower_bound(arr, target)
}
fn lower_bound(arr: &[i32], target: i32) -> usize {
let mut left = 0;
let mut right = arr.len();
while left < right {
let mid = left + (right - left) / 2;
if arr[mid] < target {
left = mid + 1;
} else {
right = mid;
}
}
left
}
fn main() {
let arr = vec![1, 3, 5, 7];
println!("{}", find_insertion_position(&arr, 4)); // 2
println!("{}", find_insertion_position(&arr, 0)); // 0
println!("{}", find_insertion_position(&arr, 8)); // 4
}
Search in Rotated Sorted Array
A sorted array rotated at some pivot:
fn search_rotated(nums: &[i32], target: i32) -> i32 {
let mut left = 0;
let mut right = nums.len() as i32 - 1;
while left <= right {
let mid = left + (right - left) / 2;
let mid_idx = mid as usize;
if nums[mid_idx] == target {
return mid;
}
// Determine which half is sorted
if nums[left as usize] <= nums[mid_idx] {
// Left half is sorted
if nums[left as usize] <= target && target < nums[mid_idx] {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
// Right half is sorted
if nums[mid_idx] < target && target <= nums[right as usize] {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
-1
}
fn main() {
let arr = vec![4, 5, 6, 7, 0, 1, 2];
println!("{}", search_rotated(&arr, 0)); // 4
println!("{}", search_rotated(&arr, 3)); // -1
}
Rotated array: [4, 5, 6, 7, 0, 1, 2]
└──sorted──┘ └sorted┘
pivot ↗
Original was [0, 1, 2, 4, 5, 6, 7], rotated at index 4
Find Minimum in Rotated Array
fn find_min_rotated(nums: &[i32]) -> i32 {
let mut left = 0;
let mut right = nums.len() - 1;
while left < right {
let mid = left + (right - left) / 2;
if nums[mid] > nums[right] {
// Minimum is in right half
left = mid + 1;
} else {
// Minimum is in left half (including mid)
right = mid;
}
}
nums[left]
}
fn main() {
println!("{}", find_min_rotated(&vec![4, 5, 6, 7, 0, 1, 2])); // 0
println!("{}", find_min_rotated(&vec![3, 1, 2])); // 1
}
Peak Element (Local Maximum)
Find an element greater than its neighbors:
fn find_peak_element(nums: &[i32]) -> usize {
let mut left = 0;
let mut right = nums.len() - 1;
while left < right {
let mid = left + (right - left) / 2;
if nums[mid] < nums[mid + 1] {
// Ascending, peak is on right
left = mid + 1;
} else {
// Descending or peak, check left
right = mid;
}
}
left
}
fn main() {
println!("{}", find_peak_element(&vec![1, 2, 3, 1])); // 2 (element 3)
println!("{}", find_peak_element(&vec![1, 2, 1, 3, 5, 6, 4])); // 5 (element 6)
}
Multiple Peaks
This finds a peak, not necessarily the highest peak. The problem guarantees at least one peak exists, and binary search will find one of them.
Square Root (Integer)
Find the largest integer whose square is ≤ n:
fn sqrt_int(n: i32) -> i32 {
if n < 2 {
return n;
}
let mut left = 1;
let mut right = n / 2;
while left <= right {
let mid = left + (right - left) / 2;
let square = (mid as i64) * (mid as i64);
if square == n as i64 {
return mid;
} else if square < n as i64 {
left = mid + 1;
} else {
right = mid - 1;
}
}
right // Largest integer with square <= n
}
fn main() {
println!("{}", sqrt_int(8)); // 2
println!("{}", sqrt_int(16)); // 4
}
Search for Condition (Abstract Binary Search)
Binary search works for any monotonic condition:
fn binary_search_condition<F>(lo: i32, hi: i32, condition: F) -> i32
where
F: Fn(i32) -> bool,
{
// Find first value where condition is True
let mut lo = lo;
let mut hi = hi;
while lo < hi {
let mid = lo + (hi - lo) / 2;
if condition(mid) {
hi = mid;
} else {
lo = mid + 1;
}
}
lo
}
fn main() {
// Example: Find first number >= 100 where checking is expensive
let is_valid = |x: i32| x >= 100;
println!("{}", binary_search_condition(0, 1000, is_valid)); // 100
}
Minimum in Mountain Array
Mountain array: increases then decreases. Find the peak:
fn peak_index_in_mountain(arr: &[i32]) -> usize {
let mut left = 0;
let mut right = arr.len() - 1;
while left < right {
let mid = left + (right - left) / 2;
if arr[mid] < arr[mid + 1] {
left = mid + 1;
} else {
right = mid;
}
}
left
}
fn main() {
println!("{}", peak_index_in_mountain(&vec![0, 2, 1, 0])); // 1
println!("{}", peak_index_in_mountain(&vec![0, 10, 5, 2])); // 1
}
Capacity to Ship Packages
Given package weights and days, find minimum ship capacity:
fn ship_within_days(weights: &[i32], days: i32) -> i32 {
fn can_ship(weights: &[i32], capacity: i32, days: i32) -> bool {
let mut current_load = 0;
let mut days_needed = 1;
for &weight in weights {
if current_load + weight > capacity {
days_needed += 1;
current_load = weight;
} else {
current_load += weight;
}
}
days_needed <= days
}
let mut left = *weights.iter().max().unwrap(); // Must hold largest package
let mut right: i32 = weights.iter().sum(); // Ship all in one day
while left < right {
let mid = left + (right - left) / 2;
if can_ship(weights, mid, days) {
right = mid;
} else {
left = mid + 1;
}
}
left
}
fn main() {
let weights = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
println!("{}", ship_within_days(&weights, 5)); // 15
}
Template Summary
| Problem Type | Condition | Move left/right | |--------------|-----------|-----------------| | Exact match | arr[mid] == target | found | | Lower bound | arr[mid] < target | left = mid + 1 | | Upper bound | arr[mid] <= target | left = mid + 1 | | First True | condition(mid) | right = mid | | Last True | condition(mid) | left = mid + 1 |
Key Takeaways
- Lower bound: first index >= target
- Upper bound: first index > target
- For duplicates: use lower/upper bounds to find range
- Rotated arrays: check which half is sorted
- Binary search works on any monotonic condition
- Many optimization problems can be solved with binary search on the answer
Master these patterns and you'll recognize when binary search applies to seemingly unrelated problems. The key insight: if you can define a condition that changes from false to true (or vice versa) at some point, binary search can find that boundary efficiently.