Why Binary Search Only Works on Sorted Data (Mathematical Proof)

Binary search requires sorted data. Everyone knows this rule, but why is it true? Understanding the mathematical reason helps you recognize when binary search applies and when it doesn't.

The answer lies in monotonicity—the property that allows us to eliminate half the search space with confidence.

TL;DR

Binary search requires monotonicity: If arr[mid] < target, all elements to the left must also be < target.

Sorted data provides monotonicity: In a sorted array, if arr[mid] < target, then arr[0], arr[1], ..., arr[mid-1] are all < target.

Unsorted data breaks monotonicity: We can't determine which half contains the target.

The Monotonicity Requirement

What Is Monotonicity?

Monotonicity means the array has a consistent ordering property that allows greedy elimination.

For binary search:

• If arr[mid] < target, we need all elements in [left, mid] to be < target
• If arr[mid] > target, we need all elements in [mid, right] to be > target

This allows us to eliminate half the array with confidence.

Visual Example (Sorted)

Sorted array: [1, 3, 5, 7, 9, 11, 13]
Target: 10

mid = 3, arr[mid] = 7

Since 7 < 10:
  All elements left of mid: [1, 3, 5] are < 7 < 10
  → Can safely eliminate left half
  → Search right half: [9, 11, 13]

What Breaks on Unsorted Data

Unsorted array: [3, 7, 1, 9, 5]
Target: 5

mid = 2, arr[mid] = 1

Since 1 < 5:
  Binary search says: eliminate left half
  But left half contains [3, 7]
  7 > 5, so we'd eliminate the wrong half!

Mathematical Proof

Theorem

Binary search requires a monotonic property: For any index i < j, if we eliminate the range [i, j], we must be certain the target is not in that range.

Proof for Sorted Arrays

Given: Sorted array arr where arr[i] <= arr[i+1] for all i

Claim: If arr[mid] < target, then target is not in [left, mid]

Proof:

1. For any index i in [left, mid], we have i <= mid
2. Since array is sorted: arr[i] <= arr[mid] (monotonic property)
3. We know arr[mid] < target
4. Therefore: arr[i] <= arr[mid] < target
5. So arr[i] < target for all i in [left, mid]
6. Therefore, target is not in [left, mid] ∎

Similarly for arr[mid] > target: Target is not in [mid, right]

Why Unsorted Arrays Fail

Counter-example:

Array: [3, 2, 4], target = 2

mid = 1, arr[mid] = 2
2 == 2 → Found!

But what if target = 4?

mid = 1, arr[mid] = 2
2 < 4 → Binary search eliminates left half [3, 2]

But 3 < 4 is FALSE!
We eliminated index 0 which could contain values > mid
→ Binary search fails

The problem: Without sorting, arr[i] <= arr[mid] doesn't hold for i < mid.

Visual Proof

Sorted Array (Works)

Array: [1, 3, 5, 7, 9]
        ↑        ↑
      left     right

mid = 2, arr[mid] = 5, target = 7

Decision: 5 < 7 → search right

Why this is safe:
  [1, 3, 5] are all < 5 < 7
  ↓
  Target cannot be in left half
  ✓ Correct elimination

Unsorted Array (Fails)

Array: [3, 1, 5, 2, 4]
        ↑        ↑
      left     right

mid = 2, arr[mid] = 5, target = 3

Decision: 5 > 3 → search left

Why this fails:
  Right half: [2, 4]
  4 > 3, so target could be there!
  ✗ Wrong elimination

When You Can Use Binary Search on "Unsorted" Data

Monotonic Functions

Binary search works on any monotonic function, not just sorted arrays.

Example: Square root

def sqrt(x):
    left, right = 0, x
    
    while left <= right:
        mid = left + (right - left) // 2
        square = mid * mid
        
        if square == x:
            return mid
        elif square < x:
            left = mid + 1  # Larger mid needed
        else:
            right = mid - 1  # Smaller mid needed
    
    return right

# Works because f(x) = x² is monotonic increasing

Why this works: f(x) = x² is monotonically increasing for x >= 0, so if mid² < target, all values < mid also have squares < target.

Binary Search on Answer

Example: Koko Eating Bananas

def minEatingSpeed(piles, h):
    def can_finish(speed):
        hours = sum((pile + speed - 1) // speed for pile in piles)
        return hours <= h
    
    left, right = 1, max(piles)
    
    while left < right:
        mid = left + (right - left) // 2
        if can_finish(mid):
            right = mid  # Try slower
        else:
            left = mid + 1  # Need faster
    
    return left

# Works because feasibility is monotonic:
# If speed k works, speed k+1 also works

Why this works: The feasibility function is monotonic—if Koko can finish with speed k, she can finish with any speed > k.

Common Misconceptions

Misconception 1: "Binary search only works on arrays"

False. Binary search works on any monotonic search space, including:

• Sorted arrays
• Monotonic functions (sqrt, log, etc.)
• Answer spaces with monotonic feasibility

Misconception 2: "I can use binary search if I sort first"

Partially true. You can sort, but:

• Sorting costs O(n log n)
• You lose original indices
• For single search, linear search (O(n)) is faster

Misconception 3: "Rotated arrays aren't sorted, so binary search doesn't work"

False. Rotated arrays have partial monotonicity—one half is always sorted. We can identify the sorted half and use binary search logic on it.

Decision Framework

Can I use binary search?
│
├─ Is data sorted?
│  ├─ Yes → Binary search ✓
│  └─ No → Continue
│
├─ Can I sort the data?
│  ├─ Yes, and I don't need original indices → Sort, then binary search ✓
│  └─ No, or I need original indices → Continue
│
├─ Is there a monotonic property?
│  ├─ Yes (e.g., monotonic function, feasibility) → Binary search ✓
│  └─ No → Use linear search or hash map ✗

Examples

Example 1: Two Sum (Unsorted)

# Array: [3, 2, 4], target = 6

# Binary search? NO
# - Array is unsorted
# - Need original indices (can't sort)
# - No monotonic property

# Solution: Hash map
def twoSum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        if target - num in seen:
            return [seen[target - num], i]
        seen[num] = i

Example 2: Two Sum II (Sorted)

# Array: [2, 7, 11, 15], target = 9

# Binary search? YES (using two pointers)
# - Array is sorted
# - Monotonic property holds

def twoSum(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        current = numbers[left] + numbers[right]
        if current == target:
            return [left + 1, right + 1]
        elif current < target:
            left += 1  # Need larger sum
        else:
            right -= 1  # Need smaller sum

Example 3: Find Peak Element

# Array: [1, 2, 3, 1] (not fully sorted)

# Binary search? YES
# - Has monotonic property: if arr[mid] < arr[mid+1], peak is to the right

def findPeakElement(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < nums[mid + 1]:
            left = mid + 1  # Peak is to the right
        else:
            right = mid  # Peak is to the left or at mid
    return left

FAQ

Q: Can I use binary search on a partially sorted array?

A: Only if you can identify a monotonic property. For example, rotated sorted arrays have one sorted half.

Q: What if I sort the array first?

A: You can, but:

• Sorting costs O(n log n)
• You lose original indices
• For single search, linear search is faster

Q: Does binary search work on linked lists?

A: Technically yes, but it's inefficient (O(n) to access middle element). Better to use linear search or convert to array.

Q: Can I use binary search to find the maximum element?

A: Not directly. Binary search finds a target, not extrema. Use linear search (O(n)) or specialized algorithms.

Conclusion

Binary search requires monotonicity—a property that allows safe elimination of half the search space.

Sorted arrays provide monotonicity:

• If arr[mid] < target, all elements <= mid are < target
• We can eliminate the left half with confidence

Unsorted arrays lack monotonicity:

• We can't determine which half contains the target
• Binary search fails

Beyond sorted arrays:

• Binary search works on any monotonic search space
• Monotonic functions, answer spaces with monotonic feasibility

Decision rule:

• Sorted or monotonic → Binary search ✓
• Unsorted and no monotonic property → Linear search or hash map

Understanding this principle helps you recognize when binary search applies, even in non-obvious scenarios. For more details, see Binary Search vs Linear Search and the Complete Binary Search Guide.