Binary search strategy

Personal site

Personal independent blog site ：https://wzzzx.github.io/
The subsequent consideration is to maintain independent blogs .

Two point search strategy

When looking for a specific value in an ordered array , Binary search method is a very common and efficient idea , This method is also called half search （Binary Search）, It is an efficient search method , It can complete the search within the logarithmic time complexity of data scale . But when implementing binary search , Boundary condition judgment , Subscript change calculation and other places are prone to problems , These errors will directly cause the code to enter an endless loop or crash . therefore , In addition to understanding the algorithm at the algorithm level , At the code level, we also need why , To master the algorithm completely .

For the problem of binary search , In general, it can be divided into two categories , The first is to find a value that is the same as the given value , The second is to find the first or last value that is the same as the given value . In fact, they are all in one Specific interval Search repeatedly in half .

Find a specific value

Finding a specific value is one of the most common operations . Let's first look at an algorithm that is logically correct , The comments in the code mark the five most problematic places

int binarySearch(const vector<int> &vec, int target) {
    int left = 0;
    int right = vec.size() - 1;                  // 1

    while (left <= right) {                      // 2
        int mid = left + (right - left) / 2;     // 3
        int val = vec[mid];
        if (val == target) {
            return mid;
        }
        else if (val < target) {
            left = mid + 1;                      // 4
        }
        else if (val > target) {
            right = mid - 1;                     // 5
        }
    }

    return -1;
}

The third point

This is the simplest point to understand , So put it at the front .

When two numbers are added , Be sure to pay attention to overflow error . Generally, it can be converted to unsigned long long Calculate , But this extra conversion can be avoided by the difference between the two subscripts .

The first point

The first point is the most important , This initial value decision How to write the subsequent error prone code .

Except for the example code vec.size() - 1, The value here can also be vec.size(). These two values change the algorithm Search range . When the value is vec.size() - 1 when , Algorithm in Closed interval Internal search , Values are located in [left, right] in . When the value is vec.size() when , The algorithm will be in Left closed right open interval Internal search , Values in the [left, right) in . The latter also means right Always point to a nonexistent value .

When Search range After it can be determined , The subsequent code is actually easy to determine .

Second point

When Search range After the concept can be understood , How to write here is actually easy to understand .

When the search interval is a Closed interval When ,left and right The values pointed to are Accessible and not accessed Of . As the search goes on , These two subscripts will gradually approach . After a round of search, the subscript changed , The most extreme situation is left be equal to right 了 . But at this time , The value they point to has not been searched . Here you can construct a size of 1 Arrays of help understand . When initializing ,left and right All are 0, At this time, you need to conduct a search to judge the results . So in this circular judgment condition ,left == right Cannot jump out of the loop . So in this case , The judgment condition of the cycle is left <= right.

When the search interval is a Left closed right open interval when ,left Pointing to Accessible and not accessed Of , but right The value pointed to is not accessible . In the implementation of standard library , Left closed right open interval right Usually used to mark the end node . alike , As the search goes on , These two values will keep approaching . Here you can also use a size of 1 To understand . When initializing ,left yes 0,right yes 1. In this extreme case ,left Strictly less than right. If you search at this time , Once found left The value pointed to is not the target value , After the subscript is changed , The value of the two is the same , Search ends .

In short , The condition for the search to continue is left < right, There's no doubt about that . however left Can it be equal to right It depends on the search interval , Under different intervals ,right The meaning represented is different .

Fourth and fifth

alike , The fourth and fifth points are also related to the search interval .

When the search interval is Closed interval When , The two sub intervals should be divided into [left, mid - 1] and [mid + 1, right].

When the search interval is Left closed right open interval When , The two sub intervals should be divided into [left, mid) and [mid + 1, right).

No matter in which search interval , Any number should only be searched once . On this basis , The two sub intervals divided should be consistent with the original interval , In this way, we can ensure that only one number is excluded at a time and the subsequent search interval is correct .

Find the left boundary of a specific value

For arrays [1,2,2,2,3],target = 2 When , The above algorithm can only return 2 The index of the value . If you want to find 2 The left boundary of this target value , The algorithm needs to be modified .

Let's first look at the sample code ：

int leftBound(const vector<int>& vec, int target) {
    int left = 0;
    int right = vec.size();

    while (left < right) {
        int mid = left + (right - left) / 2;
        int val = vec[mid];
        if (val == target) {
            right = mid;                //  a key 
        }
        else if (val < target) {
            left = mid + 1;
        }
        else if (val > target) {
            right = mid;
        }
    }

    return left;
}

principle

The reason why this algorithm can find the left boundary , The focus is on the sentence marked by the comment . Every time the target value is found , Will change the search interval to [left, mid), Keep shrinking to the left , Until all the target values are found .

Because the search interval is a left closed and right open interval , So the exit condition of search is left < right, The reason is the same as the algorithm for finding the target value . It can also be judged from this , The exit condition is left == right, So finally, when returning , You can return any variable .

Return value

The value returned by the interface looking for the left boundary actually has a special meaning , namely Less than How many target values are there . So for arrays [1, 2, 2, 2, 3] The return value of can be explained as follows ：

1. When the target value is 0 when , return 0, Indicates that the array has 0 Less than 0 Number of numbers
2. When the target value is 1 when , return 0, Indicates that the array has 0 Less than 1 Number of numbers
3. When the target value is 2 when , return 1, Indicates that the array has 1 Less than 2 Number of numbers
4. When the target value is 4 when , return 5, Indicates that the array has 5 Less than 5 Number of numbers

But this also brings a problem . When the return value is 0 When , Does the target value exist in the array ？ So we need to break the special meaning of the return value of the left boundary , Let the interface return value only be used to determine the specific subscript of the left boundary of the target value . Once the target value does not exist , Then return to -1.

The modified code is as follows ：

int leftBound(const vector<int>& vec, int target) {
    int left = 0;

    // ...

    if (left >= vec.size()) return -1;
    if (vec[left] != target) return -1;
    return left;
}

Briefly explain these two codes .

• first if It is used to exclude the case that the values in the array are less than the target value , here left The value of will be equal to the size of the array
• the second if Judgment is used to distinguish when left == 0 when , It is impossible to distinguish whether the target value is less than all the values of the array or whether the left bound of the target value is just located in 0 The situation of

Find the right boundary of a specific value

Let's look at the sample code first . Be careful ！ The code is not complete ：

int rightBound(const vector<int>& vec, int target) {
    int left = 0;
    int right = vec.size();

    while (left < right)
    {
        int mid = left + (right - left) / 2;
        int val = vec[mid];
        if (val == target) {
            left = mid + 1;
        }
        else if (val < target) {
            left = mid + 1;
        }
        else if (val > target) {
            right = mid;
        }
    }

    return right;
}

principle

The principle of this algorithm is the same as that of finding the left boundary . Every time we find the target value , Change the search interval to [mid + 1, right), Keep shrinking the left boundary , Directly meet the exit conditions .

Return value

It can be seen from the principle of the algorithm , Each time the target value is found, the left boundary will shrink . So if you don't operate , The final return value is actually the subscript of the first value greater than the target value , The return value indicates that Less than or equal to The number of elements of the target value . So for arrays [1, 2, 2, 2, 3] The return value of can be explained as follows ：

1. When the target value is 0 when , return 0, Indicates that the array has 0 Less than or equal to 0 Number of numbers
2. When the target value is 2 when , return 4, Indicates that the array has 4 Less than or equal to 2 Number of numbers
3. When the target value is 3 when , return 5, Indicates that the array has 5 Less than or equal to 3 Number of numbers
4. When the target value is 4 when , return 5, Indicates that the array has 5 Less than or equal to 4 Number of numbers

If you want to find the subscript value of the right boundary , These return values are obviously incorrect . So it needs to be slightly modified , As shown below ：

int rightBound(const vector<int>& vec, int target) {
    // ...

    if (right == 0) return -1;
    if (vec[right - 1] != target) return -1;
    return right - 1;               //  a key 
}

A brief explanation of this code ：

1. first if Used to exclude cases where the target value is smaller than the value in the array ;
2. the second if Used to exclude cases where the target value is larger than the value in the array

What needs to be focused on is the return value statement marked by the annotation , Here are three ways to understand ：

1. from right The meaning indicated by the return value is known , The correct subscript of the right boundary should be right - 1;
2. Every time we find the target value , The left boundary will be shrunk once , The code of this operation is left = mid + 1. So a simple transformation here can calculate ,mid = left - 1;
3. In this algorithm , The search interval is left closed and right open , It means right The location pointed to is inaccessible , You need to move one bit to the left to access

Code of other search intervals

There are two kinds of search intervals for binary search , Only one of them is used in the above explanation , Now the codes of the three algorithms under different search intervals are shown below ：

Find a specific value

int binarySearch(const vector<int>& vec, int target) {
    int left = 0;
    int right = vec.size();

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

    return -1;
}

Find the left boundary of a specific value

int leftBound(const vector<int>& vec, int target) {
    int left = 0;
    int right = vec.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        int val = vec[mid];
        if (val == target) {
            right = mid - 1;
        }
        else if (val < target) {
            left = mid + 1;
        }
        else if (val > target) {
            right = mid - 1;
        }
    }

    if (left >= vec.size()) return -1;
    if (vec[left] != target) return -1;
    return left;
}

Find the right boundary of a specific value

int rightBound(const vector<int>& vec, int target) {
    int left = 0;
    int right = vec.size() - 1;

    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        int val = vec[mid];
        if (val == target) {
            left = mid + 1;
        }
        else if (val < target) {
            left = mid + 1;
        }
        else if (val > target) {
            right = mid - 1;
        }
    }

    if (right < 0) return -1;
    if (vec[right] != target) return -1;
    return right;
}

Pay attention here , When the target value is less than all the values in the array ,right The value of will be less than 0, Therefore, evasion is required here .

summary

From the above explanation, we can see , The key to correct code is Search range . Only on the basis of understanding the search interval , Can write the corresponding code correctly .

The logic of finding a specific value is the same as that of finding the left and right boundaries , Is to find a specific value , However, you need to pay extra attention to the return value of the boundary when looking for the boundary , And fault tolerant processing .