Binary Search Advanced - The Two-Segment Property

Introduction

In the Binary Search Fundamentals article, we learned how to apply binary search on sorted arrays. But what if I told you binary search can work on unsorted arrays too?

Many people believe binary search requires a sorted array. This is a misconception. The real requirement is something more fundamental.

❌ Wrong: Binary search only works on sorted arrays
✅ Right: Binary search works when you can divide into two segments

This insight opens up a whole new world of problems that can be solved with binary search!

The Two-Segment Property

What is Two-Segment Property?

For any position i in the search space, if we can define a condition f(i) such that:

f(0), f(1), ..., f(k-1) = FALSE
f(k), f(k+1), ..., f(n-1) = TRUE

Then the search space has the two-segment property, and we can use binary search to find k.

Visual Understanding

Traditional sorted array:
Index:  0   1   2   3   4   5   6   7   8
Value:  1   3   5   7   9  11  13  15  17
        ←─── < 9 ───→  ←───── >= 9 ─────→
        
Rotated sorted array:
Index:  0   1   2   3   4   5   6   7
Value:  4   5   6   7   0   1   2   3
        ←─ >= nums[0] ─→ ←─ < nums[0] ─→
        
Peak finding:
Index:  0   1   2   3   4   5   6
Value:  1   3   5   7   4   2   1
        ←── ascending ──→ ←─ desc ─→

All three have the two-segment property, so binary search works!

Key Principle

💡 Find the right condition: Once you identify the condition that divides the search space into two segments, the binary search template applies directly.

Problem 1: Search in Rotated Sorted Array (LC 33)

Problem

Search for a target in an array that was originally sorted but then rotated at some pivot.

Input:  nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Input:  nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Key Insight

Even though the array is not fully sorted, it has the two-segment property:

Array: [4, 5, 6, 7, 0, 1, 2]
        ←── >= 4 ──→ ←─ < 4 ─→
        
At any point, at least one half is sorted!
- If nums[left] <= nums[mid]: left half is sorted
- Otherwise: right half is sorted

Step-by-Step Example

nums = [4, 5, 6, 7, 0, 1, 2], target = 0

Step 1: left=0, right=6, mid=3
        nums[mid] = 7
        nums[left]=4 <= nums[mid]=7 → left half [4,5,6,7] is sorted
        Is 0 in [4,7)? No → search right half
        left = 4

Step 2: left=4, right=6, mid=5
        nums[mid] = 1
        nums[left]=0 <= nums[mid]=1 → left half [0,1] is sorted
        Is 0 in [0,1)? Yes! → search left half
        right = 4

Step 3: left=4, right=4, mid=4
        nums[mid] = 0 == target ✓
        return 4

Solution

Complexity

• Time: O(log n)
• Space: O(1)

Problem 2: Find Minimum in Rotated Sorted Array (LC 153)

Problem

Find the minimum element in a rotated sorted array.

Input:  nums = [3,4,5,1,2]
Output: 1

Input:  nums = [4,5,6,7,0,1,2]
Output: 0

Key Insight

The two-segment property is clear:

Array: [4, 5, 6, 7, 0, 1, 2]
        ←── > right ──→ ←── <= right ──→
                        ↑
                     minimum

Condition: nums[mid] > nums[right]
- TRUE: minimum is in the right half
- FALSE: minimum is in the left half (including mid)

Solution

Why Compare with right?

Comparing with nums[left] doesn’t work for non-rotated arrays:

Non-rotated: [1, 2, 3, 4, 5]
nums[mid]=3 >= nums[left]=1  → Would go right, but min is at left!

Compare with right:
nums[mid]=3 <= nums[right]=5 → Goes left correctly ✓

Problem 3: Find Peak Element (LC 162)

Problem

Find a peak element where nums[i] > nums[i-1] and nums[i] > nums[i+1]. Assume nums[-1] = nums[n] = -∞.

Input:  nums = [1,2,3,1]
Output: 2 (index of peak value 3)

Input:  nums = [1,2,1,3,5,6,4]
Output: 5 (or 1, both are valid)

Key Insight

The array can be unsorted, but still has the two-segment property:

Array: [1, 2, 1, 3, 5, 6, 4]
                        ↑ peak
                        
At each mid, compare with mid+1:
- nums[mid] > nums[mid+1]: descending slope → peak is on left (including mid)
- nums[mid] < nums[mid+1]: ascending slope → peak is on right

This guarantees we find A peak (not necessarily the highest).

Visual Proof

Why does this always find a peak?

Case 1: Ascending at mid
    nums[mid] < nums[mid+1]
    
        ?
       /
      mid
      
    We go right. Since nums[n] = -∞, we must eventually 
    find a peak before going off the edge.

Case 2: Descending at mid
    nums[mid] > nums[mid+1]
    
    mid
      \
       ?
       
    We go left (including mid). Since nums[-1] = -∞, 
    we must eventually find a peak before going off the edge.

Solution

Complexity

• Time: O(log n)
• Space: O(1)

Problem 4: Kth Smallest Element in a Sorted Matrix (LC 378)

Problem

Find the kth smallest element in an n×n matrix where each row and column is sorted.

Matrix:
[1,  5,  9]
[10, 11, 13]
[12, 13, 15]

k = 8
Output: 13 (8th smallest element)

Key Insight

This is binary search on the value space, not the index space!

Value range: [matrix[0][0], matrix[n-1][n-1]] = [1, 15]

For any value mid:
- Count elements ≤ mid
- If count < k: answer > mid
- If count >= k: answer ≤ mid

This is the two-segment property on the VALUE space!

Counting Elements Efficiently

Use the staircase method from the bottom-left corner:

Target = 11

[1,  5,  9]      Start: row=2, col=0
[10, 11, 13]     
[12, 13, 15]     12 > 11, go up
 ↑
 
[1,  5,  9]      10 <= 11, count += 2, go right
[10, 11, 13]     
 →
 
[1,  5,  9]      11 <= 11, count += 2, go right
    [10, 11, 13]     
         →
         
[1,  5,  9]      13 > 11, go up
    [10, 11, 13]     
             ↑
             
[1,  5,  9]      9 <= 11, count += 1, go right
         →
         
Out of bounds. Total count = 5

Solution

Complexity

• Time: O(n × log(max - min))
• Space: O(1)

Binary Search on Answer Space

A powerful pattern: when asked to find a minimum/maximum value that satisfies a condition, binary search on the answer space!

Pattern Recognition

Look for these keywords:

• “Find the minimum X such that…”
• “Find the maximum Y that can…”
• “What is the smallest/largest value…”

General Template

function findOptimalAnswer(problem) {
  let left = minPossibleAnswer;
  let right = maxPossibleAnswer;
  
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    
    if (canAchieve(problem, mid)) {
      // Found a valid answer, try to find a better one
      right = mid;  // for minimum
      // left = mid + 1;  // for maximum (with modifications)
    } else {
      left = mid + 1;
    }
  }
  
  return left;
}

Problem 5: Koko Eating Bananas (LC 875)

Problem

Koko can eat k bananas per hour. Given piles of bananas and h hours, find the minimum k to eat all bananas.

Input:  piles = [3,6,7,11], h = 8
Output: 4

Explanation: 
With k=4: ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8 hours ✓

Key Insight

Binary search on the eating speed (answer space):

Speed range: [1, max(piles)]

For any speed k:
- Calculate hours needed
- If hours <= h: speed is fast enough, try slower
- If hours > h: speed is too slow, try faster

Two-segment property:
[1, 2, ..., k-1] = too slow (hours > h)
[k, k+1, ..., max] = fast enough (hours <= h)

Solution

Complexity

• Time: O(n × log(max(piles)))
• Space: O(1)

Problem 6: Capacity to Ship Packages Within D Days (LC 1011)

Problem

Find the minimum ship capacity to ship all packages within D days.

Input:  weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15

Explanation:
Day 1: 1,2,3,4,5 (sum=15)
Day 2: 6,7 (sum=13)
Day 3: 8 (sum=8)
Day 4: 9 (sum=9)
Day 5: 10 (sum=10)

Key Insight

Binary search on the ship capacity:

Capacity range: [max(weights), sum(weights)]
- Minimum: must fit the largest single package
- Maximum: ship everything in one day

For any capacity c:
- Count days needed
- If days <= D: capacity is enough, try smaller
- If days > D: capacity is too small, try larger

Solution

Complexity

• Time: O(n × log(sum - max))
• Space: O(1)

Pattern Recognition Guide

When to Use Binary Search on Two-Segment Property

Red Flags That Suggest Binary Search

1. Sorted or partially sorted data
2. Minimum/maximum optimization
3. “At least” or “at most” constraints
4. Answer can be verified in O(n) or less

Template Summary

// Type 1: Search in modified sorted array
while (left <= right) {
  const mid = ...;
  if (found) return mid;
  // Determine which half to search based on two-segment property
}

// Type 2: Find boundary (minimum satisfying condition)
while (left < right) {
  const mid = ...;
  if (condition(mid)) {
    right = mid;  // Found valid, try smaller
  } else {
    left = mid + 1;  // Not valid, need larger
  }
}
return left;

// Type 3: Find boundary (maximum satisfying condition)
while (left < right) {
  const mid = left + Math.floor((right - left + 1) / 2);  // Note: +1
  if (condition(mid)) {
    left = mid;  // Found valid, try larger
  } else {
    right = mid - 1;  // Not valid, need smaller
  }
}
return left;

Summary

🎯 Key Takeaways

1. Two-segment property is the essence: Binary search works whenever you can divide the search space into two distinct segments

2. Not just for sorted arrays: Rotated arrays, peak finding, and answer space problems all use binary search

3. Binary search on answer space: When finding optimal value, search on the answer range with a verification function

4. Pattern recognition:

   • Modified sorted array → Compare with boundaries
   • Find minimum satisfying X → while (l < r), right = mid
   • Find maximum satisfying X → while (l < r), left = mid

📊 Problem Classification

💡 Interview Tips

1. Identify the two segments first before writing code
2. Clearly define the condition that separates the segments
3. Choose the right template based on whether finding min or max
4. Verify with edge cases: empty array, single element, all same values

🎯 Master binary search by understanding its essence: it’s not about sorting, it’s about dividing into two segments!

📚 Related Articles

• Binary Search Fundamentals - Master the basic templates