Binary Search and Monotonic Function
In the preceding binary search problems, the arrays are always sorted. We stated that we can use binary search whenever we make a binary decision to shrink the search range. This might sound a little abstract. In this module, we will dive a little further into when we can use binary search.
Monotonic Function
A monotonic function is a function that is either non-decreasing or non-increasing. Given x1 and x2 where x1 > x2,
we should have f(x1) >= f(x2).
A sorted array is monotonic because the value increases or stays the same as the index increases.
If f(x) only contains Boolean values True and False and we think of true as 1 and false as 0, then a sorted Boolean array would consist of consecutive 0s and then consecutive 1s. For example, FFFFTTTTT.
Binary Search Template
feasible function
The precondition for binary search is to find a monotonic function f(x) that returns either True or False.
Then the problem becomes Find the First True in a Sorted Boolean Array that we already know how to solve using binary search.
We will call the function feasible to signify whether the element at the current index is feasible (True) or not (False) to meet the problem constraints.
1def binary_search(arr: List[int], target: int) -> int:
2 left, right = 0, len(arr) - 1
3 first_true_index = -1
4 while left <= right:
5 mid = (left + right) // 2
6 if feasible(mid):
7 first_true_index = mid
8 right = mid - 1
9 else:
10 left = mid + 1
11
12 return first_true_index
131public static int binarySearch(List<Integer> arr, int target) {
2 int left = 0;
3 int right = arr.size() - 1;
4 int firstTrueIndex = -1;
5 while (left <= right) {
6 int mid = left + (right - left) / 2;
7 if (feasible(mid)) {
8 firstTrueIndex = mid;
9 right = mid - 1;
10 } else {
11 left = mid + 1;
12 }
13 }
14 return firstTrueIndex;
15}
161public static int BinarySearch(List<int> arr, int target)
2{
3 int left = 0;
4 int right = arr.Count - 1;
5 int firstTrueIndex = -1;
6 while (left <= right)
7 {
8 int mid = (left + right) / 2;
9 if (feasible(mid))
10 {
11 firstTrueIndex = mid;
12 right = mid - 1;
13 }
14 else
15 {
16 left = mid + 1;
17 }
18 }
19 return firstTrueIndex;
20}
211function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4 let first_true_index = -1;
5
6 while (left <= right) {
7 let mid = Math.floor((left + right) / 2);
8 if (feasible(mid)) {
9 first_true_index = mid;
10 right = mid - 1;
11 } else {
12 left = mid + 1;
13 }
14 }
15 return first_true_index;
16}
171function binarySearch(arr: number[], target: number): number {
2 let left = 0;
3 let right = arr.length - 1;
4 let first_true_index = -1;
5
6 while (left <= right) {
7 let mid = Math.floor((left + right) / 2);
8 if (feasible(mid)) {
9 first_true_index = mid;
10 right = mid - 1;
11 } else {
12 left = mid + 1;
13 }
14 }
15 return first_true_index;
16}
171int binary_search(std::vector<int> arr, int target) {
2 int left = 0;
3 int right = arr.size() - 1;
4 int firstTrueIndex = -1;
5 while (left <= right) {
6 int mid = left + (right - left) / 2;
7 if (feasible(mid)) {
8 firstTrueIndex = mid;
9 right = mid - 1;
10 } else {
11 left = mid + 1;
12 }
13 }
14 return firstTrueIndex;
15}
161func binarySearch(arr []int, target int) int {
2 left := 0
3 right := len(arr) - 1
4 firstTrueIndex := -1
5 for left <= right {
6 mid := (left + right) / 2
7 if feasible(mid) {
8 firstTrueIndex = mid
9 right = mid - 1
10 } else {
11 left = mid + 1
12 }
13 }
14 return firstTrueIndex
15}
161fn binary_search(arr: &[i32], target: i32) -> i32 {
2 let mut left = 0i32;
3 let mut right = arr.len() as i32 - 1;
4 let mut first_true_index = -1;
5 while left <= right {
6 let mid = left + (right - left) / 2;
7 if feasible(mid) {
8 first_true_index = mid;
9 right = mid - 1;
10 } else {
11 left = mid + 1;
12 }
13 }
14 first_true_index
15}
161def binary_search(arr, target)
2 left = 0
3 right = arr.length - 1
4 first_true_index = -1
5 while left <= right
6 mid = (left + right) / 2
7 if feasible(mid)
8 first_true_index = mid
9 right = mid - 1
10 else
11 left = mid + 1
12 end
13 end
14 first_true_index
15end
161(define (binary-search arr target)
2 (let loop ([left 0]
3 [right (sub1 (vector-length arr))]
4 [first-true-index -1])
5 (if (<= left right)
6 (let ([mid (quotient (+ left right) 2)])
7 (if (feasible mid)
8 (loop left (sub1 mid) mid)
9 (loop (add1 mid) right first-true-index)))
10 first-true-index)))
111binarySearch :: [Int] -> Int -> Int
2binarySearch arr target = search 0 (length arr - 1) (-1)
3 where
4 search left right firstTrueIndex
5 | left <= right =
6 let mid = left + (right - left) `div` 2
7 in if feasible mid
8 then search left (mid - 1) mid
9 else search (mid + 1) right firstTrueIndex
10 | otherwise = firstTrueIndex
11Now, the problem has become finding the feasible function and then mechanically applying the template.
In the Find the First True in a Sorted Boolean Array problem, the feasible function is simply arr[mid] == True.
Finding the feasible function can be trickier in other problems. Let's look at a few examples.