Devil's Dichotomy Lookup

Posted on Edited on In Waline:

Principle

Knuth (who invented the KMP algorithm) said that dichotomous lookups are simple, but the details are the devil**. Many people like to talk about the integer overflow bug, but the real pitfall of dichotomous lookup is not that detail at all, but whether to add one or subtract one to mid, and whether to use <= or < in while.

If you do not have a proper understanding of these details, writing dichotomous is certainly metaphysical programming, there is no bug can only rely on the blessing of God.

Framework

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        int mid = left + (right - left) / 2;// 可有效防止left + right溢出
        if (nums[mid] target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

Example

Find a number

This scenario is the simplest and probably the most familiar, i.e., search for a number and return its index if it exists, otherwise return -1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1; // 注意

    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] target)
            return mid;
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
    }
    return -1;
}

1. Why is <= in the condition of the while loop instead of <?

A: Because the assignment to initialize right is nums.length - 1, which is the index of the last element, not nums.length.

The difference between these two, which may occur in dichotomous lookups with different functions, is that ** the former corresponds to the closed interval [left, right] at both ends, while the latter corresponds to the left-closed, right-open interval [left, right), since the index size of nums.length is out of bounds. **

We use in this algorithm the interval where the former [left, right] is closed at both ends. This interval is actually the interval where the search is performed each time.

When should I stop the search? Of course, it can be terminated when the target value has been found:

1
2
if(nums[mid] target)
    return mid;

But if you don’t find it, you need the while loop to terminate and return -1. When should the while loop terminate? The loop should terminate when the search interval is empty, which means you have nothing to find, which means you didn’t find it.

The termination condition of while(left <= right) is left right + 1，写成区间的形式就是 [right + 1, right]，或者带个具体的数字进去 [3, 2]，可见这时候区间为空，因为没有数字既大于等于 3 又小于等于 2 的吧。所以这时候 while 循环终止是正确的，直接返回 -1 即可。

The termination condition of while(left < right) is left right，写成区间的形式就是 [left, right]，或者带个具体的数字进去 [2, 2]，这时候区间非空，还有一个数 2，但此时 while 循环终止了。也就是说这区间 [2, 2] 被漏掉了，索引 2 没有被搜索，如果这时候直接返回 -1 就是错误的。

Of course, if you have to use while(left < right) that’s fine, we already know what’s going wrong, so let’s just patch it:

1
2
3
4
5
//...
while(left < right) {
    // ...
}
return nums[left] target ? left : -1;

In summary, if right is length - 1 at the beginning, then you need to let the case left = right be searched as well. If right is length at the beginning, the critical case left = right is actually out of the valid range of the array

**2. Why left = mid + 1, right = mid - 1? I see some code is right = mid or left = mid, there is no such addition and subtraction, what is going on and how to determine **?

A: This is also a difficult part of the dichotomous search, but as long as you can understand the previous content, you will be able to easily determine.

We have just clarified the concept of search interval', and the search interval of this algorithm is closed at both ends, i.e., [left, right]. So when we find that the index midis not thetarget` we are looking for, where should we search next?

Of course it goes to search [left, mid-1] or [mid+1, right], right? Because mid has already been searched and should be removed from the search interval.

3. What are the flaws of this algorithm?

A: At this point, you should have all the details of the algorithm and the reasons for treating it this way. However, there are limitations to this algorithm.

Let’s say you are given the ordered array nums = [1,2,2,2,3] and target is 2, this algorithm returns an index of 2, yes. But if I want to get the left-hand side of target, which is index 1, or if I want to get the right-hand side of target, which is index 3, then this algorithm can’t handle that.

This is a very common requirement, ** you may say, find a target, and then search linearly left or right, can’t you? Yes, but it’s not good, because it’s hard to guarantee the complexity of a dichotomous search on a logarithmic scale**.

Dichotomous lookup to find the left-hand boundary

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int left_bound(int[] nums, int target) {
    if (nums.length 0) return -1;
    int left = 0;
    int right = nums.length; // 注意
    
    while (left < right) { // 注意
        int mid = (left + right) / 2;
        if (nums[mid] target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}

1. Why is < in while instead of <=?

A: The same way, because right = nums.length instead of nums.length - 1. So the search interval of each loop is [left, right) left closed and right open.

while(left < right) terminates with the condition left right，此时搜索区间 [left, left) 为空，所以可以正确终止。

2. Why is there no operation that returns -1? What if the value target does not exist in nums?

A: Because we have to take one step at a time, let’s first understand what the special meaning of this “left border” is:

For this array, the algorithm returns 1. The meaning of this 1 can be interpreted as follows: there is 1 element in nums that is less than 2.

For example, for the ordered array nums = [2,3,5,7], target = 1, the algorithm will return 0, meaning that there are 0 elements in nums that are less than 1.

If we say nums = [2,3,5,7], target = 8, the algorithm will return 4, meaning that there are 4 elements in nums that are less than 8.

As you can see above, the return value of the function (i.e. the value of the left variable) takes the closed interval [0, nums.length], so we can simply add two lines of code to return -1 at the right time:

1
2
3
4
5
6
7
while (left < right) {
    //...
}
// target is larger than all numbers
if (left nums.length) return -1;
// Similar processing to the previous algorithm
return nums[left] target ? left : -1;

3. Why left = mid + 1 and right = mid? is not the same as the previous algorithm?

A: This is easy to explain, because our search interval' is [left, right)` closed left and open right, so when `nums[mid]` is detected, the next search interval should be split into two intervals by removing `mid`, i.e. `[left, mid)` or `[mid + 1, right)`.

4. Why is the algorithm able to search the left-hand side boundary?

A: The key is that for nums[mid] target 这种情况的处理：

1
2
if (nums[mid] target)
    right = mid;

It can be seen that, instead of returning immediately when the target is found, the upper bound right of the search interval is narrowed, and the search continues in the interval [left, mid), i.e., it keeps shrinking to the left to lock the left boundary.

5. Why does it return left instead of right?

A: It’s the same, because the while termination condition is left right。

**6、Can you find a way to turn right into nums.length - 1, that is, continue to use both sides of the closed search interval? This way you can and the first dichotomous search in some way unified **.

A: Of course you can, as long as you understand the concept of “search interval”, you can effectively avoid missing elements, you can change it any way you want. The following we modify strictly according to the logic:

Since you have to make both ends of the search interval closed, right should be initialized to nums.length - 1 and the terminating condition while should be left right + 1，也就是其中应该用 <=：

1
2
3
4
5
6
7
int left_bound(int[] nums, int target) {
    // The search interval is [left, right]
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        // if else ...
}

Because the search interval is closed at both ends and is now searching the left-hand boundary, the update logic for left and right is as follows:

1
2
3
4
5
6
7
8
9
10
if (nums[mid] < target) {
    // The search interval becomes [mid+1, right]
    left = mid + 1;
} else if (nums[mid] > target) {
    // The search interval becomes [left, mid-1]
    right = mid - 1;
} else if (nums[mid] target) {
    // Shrink the right border
    right = mid - 1;
}

Since the exit condition of while is left right + 1，所以当 target 比 nums 中所有元素都大时，会存在以下情况使得索引越界：

img

Therefore, the code that finally returns the result should check for out-of-bounds:

1
2
3
if (left >= nums.length || nums[left] != target)
    return -1;
return left;

At this point, the entire algorithm is written, and the complete code is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    // The search interval is [left, right]
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            // The search interval becomes [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target) {
            // The search interval becomes [left, mid-1]
            right = mid - 1;
        } else if (nums[mid] target) {
            // Shrink the right border
            right = mid - 1;
        }
    }
    // Check for out-of-bounds conditions
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}

This will be unified with the first dichotomous search algorithm, both ends are closed “search interval”, and the final return is also the value of the left variable. As long as the logic of the dichotomous search, the two forms you see which one you like to remember which it.

Dichotomous lookup to find the right-hand side boundary

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] target) {
            // Just change it here to shrink the left border
            left = mid + 1;
        }
    }
    // Here it is changed to check for right out of bounds, see the figure below
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}

Link to original article:二分法详解

Dichotomous variants (updated 2021.04.08)

Today’s leetcode question of the day is a dichotomy question, but different from the above dichotomy, here is an updated record

这是题目链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/

Here I will use the official solution directly to answer the question, except that it will be explained in more detail

An ascending array without duplicate elements, after rotation, gives the following visualization of a line graph:

The horizontal axis represents the subscripts of the array elements and the vertical axis represents the values of the array elements. The position of the minimum value is marked in the figure and is the target we need to find.

We consider the last element of the array xx: the elements to the right of the minimum (excluding the last element itself) must all have values strictly less than xx, while the elements to the left of the minimum must all have values strictly greater than xx. Thus, we can find the minimum by means of a dichotomous lookup based on this property.

In each step of the dichotomous lookup, the left boundary is low, the right boundary is high, and the midpoint of the interval is pivot, within which the minimum value lies. We compare the middle element nums[pivot] with the right boundary element nums[high], and there are three possible cases:

The first case is nums[pivot] < nums[high]. As shown in the figure below, this means that nums[pivot] is the element to the right of the minimum, so we can ignore the right half of the dichotomous lookup interval.

The second case is nums[pivot]>nums[high]. As shown in the figure below, this means that nums[pivot] is the element to the left of the minimum, so we can ignore the left half of the dichotomous lookup interval.

Since the array does not contain duplicate elements, and as long as the current interval length is not 1, pivot will not coincide with high; and if the current interval length is 11, this means that we can already end the binary lookup. So there is no case where nums[pivot]=nums[high].

1
2
3
4
5
6
7
8
9
10
11
12
13
var findMin = function(nums) {
    let low = 0;
    let high = nums.length - 1;
    while (low < high) {
        const pivot = low + Math.floor((high - low) / 2);
        if (nums[pivot] < nums[high]) {
            high = pivot;
        } else {
            low = pivot + 1;
        }
    }
    return nums[low];
};

A few questions

After reading those explanations above, you may think you understand, but there are still a few issues we need to think about:

  • What is the search interval

    According to the principle part, since high = nums.length - 1, the search interval is [low, high]

  • Why is it executed when low < high, i.e. why is it not necessary to determine when low = high?

    This is because when low = high, the length of the interval is 1, so the minimum value is this unique value, so just return it

  • Why is it comparing pivot and high instead of low

    The values at the left, center and right positions are compared in the following ways:

    left < median, median < right : no rotation, the minimum value is on the leftmost side, you can shrink the right boundary

    1
    2
    3
    Right
    Medium
    Left

    left > median, median < right : there is rotation, the minimum value is on the left half, you can shrink the right boundary

    1
    2
    3
    Left
    Right
    Medium

    left < median, median > right : there is a rotation, the minimum value is in the right half, you can shrink the left border

    1
    2
    3
    Medium
    Left
    Right

    left > median, median > right : monotonically decreasing, not possible

    1
    2
    3
    Left
    Medium
    Right

    We can analyze the above cases and compare the median and right values in just two cases. The median value is greater than the left value has to be divided into two more cases

  • Why does high = pivot and low = pivot + 1 when narrowing the interval

    Because when nums[pivot] < nums[high], this nums[pivot] is still possible to be the minimum, so pivot is still in the search interval. And when nums[pivot] > nums[high], nums[pivot] can’t be the minimum