A simple understanding of binary search

The binary search algorithm is well understood, but the various templates for binary search are cumbersome, The question of when to use left <= right, when to use left < right, when to use left = mid + 1, and when to use left = mid often puzzles us, especially if we haven’t used binary search for a long time. So there are often dichotomous details that are the devil. The main purpose of this article is to provide a simple overview of this problem, so that you can get rid of the conditional selection difficulties of binary lookup.

The key to binary search conditions

In fact, binary search conditions are not without basis, the choice of conditions actually depends on your definition of circular conditions (i.e. left and right) relationship, we take binary search common two templates for example:

  • Template 1
while (left <= right) {    // set the search interval to [left,right]
    int mid = (right - left) / 2 + left; // mid = (left + right) / 2
    if (nums[mid] > target) {
        right = mid - 1;   [left,right] = mid; [left,right] = mid;
    } else if (nums[mid] < target) {
        left = mid + 1;   [mid + 1, right] = mid + 1; [mid + 1, right] = mid + 1;
    } else {             // nums[mid] == target
        returnmid; }}Copy the code

Note: In this template, the loop condition is defined as left <= right, which means that the loop condition is still valid when left == right, which means that the search interval you select is [left, right], so that in the whole loop, Remember that the search interval is the [left, right] interval, and all the criteria are selected according to this interval. With the above comments, it is easy to understand how left and right are determined.

  • The template 2
while (left < right) {      // set the search interval to [left, right]
    int mid = (right - left) / 2 + left; // mid = (left + right) / 2
    if (nums[mid] > target) {
        right = mid;   [left, mid] = mid; [left, mid] = mid; [left, mid] = mid;
    } else if (nums[mid] < target) {
        left = mid + 1;   Left = mid + 1; left = mid + 1; left = mid + 1; left = mid + 1; left = mid + 1;
    } else {             // nums[mid] == target
        returnmid; }}Copy the code

Note: In this template, the loop condition is defined as left < right, which means that the loop condition is not valid when left == right, which means that the search interval you choose is [left, right], so that in the whole loop, Nums [mid] > target specifies the right endpoint as mid. Nums [mid] > target specifies the right endpoint as mid. Nums [mid] < target indicates that the left endpoint is mid + 1.

Binary search changes

Based on the above description, you might wonder: can I define the interval as left open right closed, left open right open? The answer is yes, as long as you make sure that throughout the loop you remember to think about endpoint changes in terms of the interval that you defined, and make sure that you search the whole interval, you’ll get the right answer. Binary search template is not invariable, according to the specific search conditions will produce different changes, therefore, What you need to do when using binary search is not to memorize the template, but to memorize the valid search interval that you defined, and as long as you make sure that all of your condition’s endpoint changes (i.e., left, right) are based on this valid search interval, you can write the correct binary. To better understand the above paragraph, take the core code of LeetCode 154 finding the minimum value II in a rotated sorted array:

        while (left <= right) {      // set the search interval to [left, right]
            if (left == right) {     // Special case handling
                return nums[left];
            }
            int mid = (right - left) / 2 + left;
            if (nums[mid] < nums[right]) {
                right = mid;
            } else if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else{ right--; }}Copy the code

A brief description of the topic of this question:

The ascending sorted array is rotated at some previously unknown point. For example, the array [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]

A simplified version of the problem in which the numbers are possible to repeat (no repeating numbers is 153). I’m not going to go into the exact solution here, just the dichotomous parts of the code.

  1. The notation here is based on template 1, and the search interval is defined as [left, right].
  2. Let’s start with the second condition:nums[mid] < nums[right]What we can infer from this condition is thatThe minimum number must be less than or equal to nums[mid], so the effective interval is[left, mid]Nums [mid] is not the minimum subscript, so mid is still a valid range. So that’s what I said,Conditions are not immutable, and endpoints vary depending on the interval, not the template.
  3. Let’s look at the third condition:nums[mid] > nums[right]What we can infer from this condition is thatThe minimum number must be less than nums[mid](at least nums[right] is less than NUMs [mid]), so the valid interval is[left + 1, mid]So left = mid + 1,The endpoints vary depending on the interval.
  4. Let’s look at the first condition: why are there new conditions? This is due to our definition of the query condition. Think about it, since right = mid in the second condition does not always narrow the search interval, therefore, in extreme cases, when left == right, special judgment may be required to ensure that all the intervals can be searched, that is, to break out of the loop. This corresponds to the other point above, make sure you search all the intervals. Of course, in this case, you could have gotten the answer without that judgment.
  5. And then just a quick word about the last else judgment, which corresponds to thisnums[left] == nums[mid] == nums[right], nums[right] is definitely not the only minimum, so move right to change the search interval. This judgment is related to the problem, not the key of dichotomy, without specific narration, you can refer to the solution of this problem.

Binary search summary

From the above analysis of binary search, I believe you have learned the two key points of binary search: identifying endpoints with search intervals and ensuring that all intervals are searched. For the second key point, it is often the case that the search criteria cannot judge 0, 1 and 2 points. According to the specific situation, it is necessary to choose whether to make a special judgment for the special case. Keeping these two key points in mind, along with proper dichotomy practice and understanding, will give you confidence in any dichotomy question.