Monotonicity and to Binary Search

The principle of monotonicity is the fundamental condition that allows the powerful Binary Search algorithm to work efficiently. Understanding this relationship is key to applying binary search beyond simple sorted arrays.

What is Monotonicity?

In mathematics and computer science, a function or a sequence is monotonic if its values, as the input increases, are either always non-decreasing or always non-increasing.

1. Monotonically Non-Decreasing (or Increasing): A sequence or function $f(x)$ is non-decreasing if, for any inputs $x_1$ and $x_2$ such that $x_1<x_2$, we have $f(x_1)\le f(x_2)$. This is characteristic of a standard sorted array in ascending order.

   • Example Array (Non-Decreasing): $[2,2,4,7,7,10]$

2. Monotonically Non-Increasing (or Decreasing): A sequence or function $f(x)$ is non-increasing if, for any inputs $x_1$ and $x_2$ such that $x_1<x_2$, we have $f(x_1)\ge f(x_2)$. This describes a sorted array in descending order.

   • Example Array (Non-Increasing): $[10,7,7,4,2,2]$

In essence, a monotonic sequence has an order that doesn’t reverse direction.

---

The Monotonicity Requirement for Binary Search

Binary search is an extremely efficient divide-and-conquer algorithm with a time complexity of $O(\log n)$. It works by repeatedly halving the search space until the target value is found or the search space is empty.

The critical insight: Binary search can only discard half of the search space with confidence if the search space is ordered, which is guaranteed by monotonicity.

1. How it Works with Monotonicity:
   • Binary search selects the middle element of the current search space.
   • It compares the middle element ($M$) to the target value ($T$).
   • If the sequence is non-decreasing and $M<T$, the target must lie in the right half (including elements greater than $M$). The left half can be safely discarded because all elements there are $\le M<T$.
   • If the sequence is non-decreasing and $M>T$, the target must lie in the left half. The right half can be safely discarded because all elements there are $\ge M>T$.

If the sequence were not monotonic (e.g., $[5,1,10]$), comparing the middle element (1) to a target (10) would give no definitive information, as the target might be to the left (5) or the right (10), forcing a linear search. Monotonicity ensures that the relationship at the midpoint applies consistently to the entire half of the array.

This principle extends to problems where you are searching for an “optimal value” (like the maximum possible value that satisfies a condition). If you can define a Boolean function (a ‘test’ or ‘feasibility check’) $f(x)$ such that once it becomes True for a value $x$, it remains True for all greater values (or smaller, in the non-increasing case), then you can binary search on the answer space.

---

Python Example: Standard Binary Search

The classic application of binary search is finding an element in a sorted array (a monotonic sequence).

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        # Find the middle index
        mid = low + (high - low) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1
 
# Example 1: Target is present (Monotonic Non-Decreasing Array)
monotonic_array_1 = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target_1 = 23
result_1 = binary_search(monotonic_array_1, target_1)
 
# Example 2: Target is NOT present
target_2 = 42
result_2 = binary_search(monotonic_array_1, target_2)
 
# Example 3: Target is present multiple times (still monotonic)
monotonic_array_2 = [1, 3, 3, 5, 5, 5, 8, 8]
target_3 = 5
result_3 = binary_search(monotonic_array_2, target_3)
 
 
# Output Examples
print(f"Array: {monotonic_array_1}, Target: {target_1}")
print(f"Output: Index {result_1} (Value: {monotonic_array_1[result_1]})")
# Output: Index 5 (Value: 23)
 
print("-" * 20)
 
print(f"Array: {monotonic_array_1}, Target: {target_2}")
print(f"Output: Index {result_2}")
# Output: Index -1
 
print("-" * 20)
 
print(f"Array: {monotonic_array_2}, Target: {target_3}")
print(f"Output: Index {result_3} (Value: {monotonic_array_2[result_3]})")
# Output: Index 3 (Value: 5)