When Binary Search Is NOT O(log n): Hidden Complexity Traps

Binary search iterations: O(log m) where m = max(piles)
Feasibility check per iteration: O(n) where n = len(piles)
Total: O(n log m)

def minEatingSpeed(piles, h):
    def can_finish(speed):
        hours = sum((pile + speed - 1) // speed for pile in piles)
        return hours <= h  # O(n) operation
    
    left, right = 1, max(piles)
    
    while left < right:  # O(log m) iterations
        mid = left + (right - left) // 2
        if can_finish(mid):  # O(n) per iteration
            right = mid
        else:
            left = mid + 1
    
    return left

# Time: O(n log m) where n = len(piles), m = max(piles)
# NOT O(log n)!

Time = O(log(answer_range) × feasibility_cost)

If feasibility is O(n): Total is O(n log m)
If feasibility is O(n²): Total is O(n² log m)

Best case: O(log n) — no ambiguity
Worst case: O(n) — must check almost all elements

def search(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if nums[mid] == target:
            return True
        
        # When all three are equal, can't eliminate half
        if nums[left] == nums[mid] == nums[right]:
            left += 1  # O(1) progress
            right -= 1  # O(1) progress
        elif nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    
    return False

# Worst case: [1, 1, 1, 1, 1, 1, 1, 0, 1]
# Almost all elements are 1, must check most of them
# Time: O(n) worst case

Array: [2, 2, 2, 2, 2, 2, 2, 0, 2]

At almost every step:
  nums[left] == nums[mid] == nums[right] = 2
  Can't determine which half is sorted
  Must shrink by 1 element at a time
  
Result: O(n) time

Start from top-right (or bottom-left)
Each step eliminates one row or one column
Worst case: eliminate all rows + all columns
Time: O(m + n)

def searchMatrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    
    rows, cols = len(matrix), len(matrix[0])
    row, col = 0, cols - 1  # Start from top-right
    
    while row < rows and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            col -= 1  # Eliminate column
        else:
            row += 1  # Eliminate row
    
    return False

# Time: O(m + n) where m = rows, n = cols
# NOT O(log(m × n))!

Matrix is NOT fully sorted:
[1,  4,  7, 11]
[2,  5,  8, 12]
[3,  6,  9, 16]
[10, 13, 14, 17]

Can't treat as 1D sorted array
Must use staircase search: O(m + n)

Find first occurrence: O(log n)
Find last occurrence: O(log n)
Return all indices: O(k) where k = count
Total: O(log n + k)

def findAllOccurrences(nums, target):
    # Find first occurrence: O(log n)
    first = lower_bound(nums, target)
    
    if first == len(nums) or nums[first] != target:
        return []
    
    # Find last occurrence: O(log n)
    last = upper_bound(nums, target) - 1
    
    # Return all indices: O(k)
    return list(range(first, last + 1))

# Time: O(log n + k) where k = number of occurrences
# If k = n (all elements are target), time is O(n)

Binary search iterations: O(log n)
String comparison per iteration: O(L) where L = string length
Total: O(L log n)

def binarySearchStrings(strings, target):
    left, right = 0, len(strings) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        # String comparison is O(L)
        if strings[mid] == target:
            return mid
        elif strings[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

# Time: O(L log n) where L = average string length
# NOT O(log n)!

How many iterations? O(log n) or O(log(max-min))?

What happens in each iteration?
- Simple comparison? O(1)
- Feasibility check? O(n), O(n²), etc.
- String comparison? O(L)

Total = iterations × per-iteration cost

def splitArray(nums, m):
    def can_split(max_sum):
        subarrays = 1
        current_sum = 0
        for num in nums:  # O(n)
            if current_sum + num > max_sum:
                subarrays += 1
                current_sum = num
            else:
                current_sum += num
        return subarrays <= m
    
    left, right = max(nums), sum(nums)
    
    while left < right:  # O(log(sum - max))
        mid = left + (right - left) // 2
        if can_split(mid):  # O(n)
            right = mid
        else:
            left = mid + 1
    
    return left

# Time: O(n log(sum - max))
# NOT O(log n)!