binary search and variations explanation intuition

binary_search.md

Normal binary search

function binary_search(A, n, T) is
    L := 0
    R := n − 1
    while L ≤ R do
        m := floor((L + R) / 2)
        if A[m] < T then // everything on the left is less, move right, i.e., delete left
            L := m + 1
        else if A[m] > T then // everything on the right is more, move left, i.e., delete right
            R := m − 1
        else:
            return m
    return unsuccessful

Binary search a value in a monotonic function

  // https://codeforces.com/contest/492/problem/B
  const long double epsilon = 1e-10;
  long double left = 0.0f;
  long right = (long double)high_limit;
  while (right - left > epsilon) {
    middle = (left + right) / 2.0f;
    if (check_valid(a, middle)) {
      // in this case everything to the right is valid
      // we are looking for the minimum, move left, i.e. delete right
      right = middle;
    } else {
      // not valid, we need to search in the right, i.e., delete left
      left = middle;
    }
  }

Leftmost element in a list with duplicates

1. Initialize left = 0 and right = array.length - 1
2. While left <= right:
   • Calculate mid = left + (right - left) / 2
   • If array[mid] < target: Move right by setting left = mid + 1
   • If array[mid] > target: Move left by setting right = mid - 1
   • If array[mid] == target:
     • Key difference: Instead of returning immediately, set right = mid - 1 to continue searching in the left half
3. After the loop, check if left is within bounds and if array[left] == target
4. Return left if target was found, otherwise return -1

Rightmost element in a list with duplicates

1. Initialize left = 0 and right = array.length - 1
2. While left <= right:
   • Calculate mid = left + (right - left) / 2
   • If array[mid] < target: Move right by setting left = mid + 1
   • If array[mid] > target: Move left by setting right = mid - 1
   • If array[mid] == target:
     • Key difference: Set left = mid + 1 to continue searching in the right half
3. After the loop, check if right is within bounds and if array[right] == target
4. Return right if target was found, otherwise return -1

Lower bound binary search

Purpose: Find the position of the first element that is greater than or equal to a target value.

1. Initialize left = 0 and right = array.length - 1
2. While left <= right:
   • Calculate mid = left + (right - left) / 2
   • If array[mid] < target:
     • Move right: left = mid + 1
   • Otherwise (when array[mid] >= target):
     • Move left: right = mid - 1
3. Return left

Key characteristics:

• If the target exists, it returns the index of the first occurrence
• If the target doesn't exist, it returns the index where it would be inserted
• Always returns a valid insertion point (between 0 and array.length)

Recursive definition

lowerBound(A, target, left, right):
  if left > right:
    return left
    
  mid = left + (right - left) / 2
  
  if A[mid] < target:
    return lowerBound(A, target, mid + 1, right)
  else:  // A[mid] >= target
    return lowerBound(A, target, left, mid - 1)

Upper bound binary search

Purpose: Find the position of the first element that is strictly greater than a target value.

1. Initialize left = 0 and right = array.length - 1
2. While left <= right:
   • Calculate mid = left + (right - left) / 2
   • If array[mid] <= target:
     • Move right: left = mid + 1
   • Otherwise (when array[mid] > target):
     • Move left: right = mid - 1
3. Return left

Key characteristics:

• Always returns the position after the last occurrence of the target
• If the target doesn't exist, behaves the same as lower bound
• Always returns a valid insertion point (between 0 and array.length)

Recursive definition

upperBound(A, target, left, right):
  if left > right:
    return left
    
  mid = left + (right - left) / 2
  
  if A[mid] <= target:
    return upperBound(A, target, mid + 1, right)
  else:  // A[mid] > target
    return upperBound(A, target, left, mid - 1)

When the base case is reached, left has been pushed just past all elements that don't satisfy our condition, placing it exactly at the boundary we seek.

What left Represents during the Search: (similar for lower bound)

Throughout the binary search, the left pointer always tracks the position of the first element that we know (based on our search so far) is strictly greater than the target.

This happens because of how we update our pointers:

1. When array[mid] <= target:

• We know that mid and everything to its left is NOT part of our answer
• So we move left = mid + 1

2. When array[mid] > target:

• We know mid might be our answer, but we need to check if there's an earlier position
• So we move right = mid - 1 to search earlier

Why left Ends at the Correct Position

When the binary search terminates (left > right), left will be pointing at:

• The first element greater than the target (if such element exists)
• The position immediately after the array's end (if all elements are ≤ target) This happens because:
• Every time we find an element ≤ target, we move left to the right of it
• Every time we find an element > target, we check if there's a better candidate to the left By the end, left has been pushed past all elements ≤ target, and sits at the first position where an element > target exists.

In Lower Bound Binary Search

In lower bound (finding first element ≥ target), the right pointer keeps track of: The index of the last element that we know is strictly less than the target value.

In Upper Bound Binary Search

In upper bound (finding first element > target), the right pointer keeps track of: The index of the last element that we know is less than or equal to the target value.

The Complementary Nature

In both algorithms, when the search terminates:

• left points to the first element satisfying our condition
• right points to the last element not satisfying our condition
• And importantly: right will always be exactly one position before left (right = left - 1)

Other considerations

Sometimes you might want to use:

while(L < R)
instead of
while(L <= R)

left = mid
right = mid

mid = (left + right + 1)/2
instead of
mid = (left + right)/2

depending on the situation, most of these change if you use L < R instead of L <= R, prefer L <= R since it's more intuitive.

Example problems

• https://codeforces.com/contest/492/problem/B (binary search a value in a monotonic function)
• https://codeforces.com/contest/1742/problem/E (upper bound binary search)