NOTE

• The above problems are quite easy to solve, because they already give us the array to be searched. We’d know that we should use binary search to solve them at first glance.
• However, more often are the situations where the search space and search target are not so readily available. Sometimes we won’t even realize that the problem should be solved with binary search — we might just turn to dynamic programming or DFS and get stuck for a very long time.
• As for the question “When can we use binary search?”, my answer is that, ==If we can discover some kind of monotonicity, for example, if condition(k) is True then condition(k + 1) is True, then we can consider binary search.==

Core Concept: Monotonicity

Monotonicity in the context of binary search means that the function or condition we are interested in exhibits a consistent behavior as we move across the search space. Specifically:

• Monotonically Increasing: If a condition is true for some k , it remains true for all k${}^{\prime }$ greater than k . Formally, if $k$ is true, then $(k+1)$ is also true. • Monotonically Decreasing: Conversely, if a condition is false for some k , it remains false for all k${}^{\prime }$ greater than k . Formally, if $k$ is false, then $(k+1)$ is also false.

The monotonicity ensures that once a certain condition is met (or not met), we don’t need to consider previous (or subsequent) elements in the search space, allowing us to effectively halve the search space in each step.

Identifying Monotonicity

To effectively use binary search, you need to identify problems where a monotonic condition exists. Here are steps to recognize such problems:

1. Define the Search Space: Identify the range of possible solutions. This could be an array index, a range of integers, or even conceptual boundaries (like the maximum value in an optimization problem).
2. Establish the Condition: Define a boolean condition or function that you want to satisfy. This condition should be something that you can evaluate for a given element in the search space.
3. Check for Monotonicity: Determine if the condition exhibits monotonic behavior: • If true for a point $k$ , it remains true (or false) for all points greater (or less) than $k$ . • Conversely, if false for a point $k$ , it remains false (or true) for all points greater (or less) than $k$.
4. Apply Binary Search: Once the monotonicity is established, you can apply binary search to efficiently find the boundary where the condition changes.

Examples of Monotonicity in Practice

1. Finding a Threshold: • Problem: Determine the maximum weight a bridge can hold without collapsing. • Search Space: Weights from $0$ to maximum limit. • Condition: The bridge can hold weight $k$ (true) or it collapses (false). • Monotonicity: If the bridge holds for $k$ , it will hold for all weights less than $k$ .
2. Optimal Value in a Sorted Array: • Problem: Find the minimum element in a rotated sorted array. • Search Space: Array indices. • Condition: Middle element is greater than or less than certain boundaries. • Monotonicity: Sorted nature provides a clear increasing or decreasing order.
3. Root Finding: • Problem: Find the square root of a number. • Search Space: Numbers from $0$ to $x$ . • Condition: Check if k${}^2$ $<=$ $x$ . • Monotonicity: If k${}^2$ $<=$ x , then for any k${}^{\prime }$ < k , (k${}^{\prime }$)${}^2$ $<=$ $x$ as well.

Practical Tips

• Transform the Problem: Sometimes you need to transform the problem to reveal monotonicity. For example, converting a maximization problem into a binary search over possible outcomes. • Binary Search on Answer: Often, instead of searching an array, you can binary search over the range of potential answers, such as in optimization problems where you’re seeking the maximum or minimum feasible solution. • Avoid Unnecessary Complexity: Ensure that the monotonicity condition can be evaluated in a reasonable time, avoiding turning an $O(\log n)$ solution into a more complex one due to costly condition checks.