Binary search algorithm ⅰ

Writing in the front

The article is summarized on the basis of predecessors plus their own understanding, only as their own learning record, not for any commercial use!

If you find any mistakes or infringement problems in this article, please point them out. Thank you!

The basic framework

public int binarySearch(int[] array, int target) {
    int left = 0;
    intright = ... ;while(...). {int mid = left + (right - left) / 2;
        if(nums[mid] == target) ... ;else if(nums[mid] < target) ... ;else if(nums[mid] > target) ... ; }return. ; }Copy the code

instructions
- When you’re doing binary search, you don’t want an else, but you want to write everything out as an else if, so you can see all the details clearly
- In the code above.And the labeled part, that’s where the details might be different, that’s where the dichotomous type of problem might be different

Find a number

Searches an array for a number, returning the index if it exists, or -1 if it does not

public int binarySearch(int[] array, int target) {
    int left = 0;
    int right = array.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (array[mid] == target) {
            return mid;
        } else if (array[mid] < target) {
            left = mid + 1;
        } else if (array[mid] > target) {
            right = mid - 1; }}return - 1;
}
Copy the code

Q1: WhywhileThe conditions for the cycle are< =Rather than<?
- First point: it can be seen that right = array. length-1, then it indicates that the value of right can be selected, that is, the interval of binary search is [left, right], so left can be equal to right
- The second point is to know when to exit the loop
  - Find the target value, which is passedarray[mid] == targetConditions directlyreturn mid
  - If no target value is found, it must passleft > rightTo exit the loop, i.eleft = right + 1There is no such interval as [right + 1, right]return -1
- Finally, third point: inright = array.length - 1If no change is required, change towhile (left < right)How do I get the right answer?
  - At this timewhileThe conditions for exiting the loop are: one is to find target, directlyreturn mid, the other is not found target, passleft = rightExit the loop
  - [left, left] [left] [left] [left] [left, so put a patch on the return:return array[left] == target ? left : -1
  - The complete code is morphing code 1
Q2: Why?left = mid + 1.right = mid - 1?
- You can see thatwhileThere are three if judgments in the loop, which obviously divide the array into three intervals: less than, equal to, and greater than, so when we find the indexmidNot to findtargetWhere should you search next?
- Search, of course[left, mid - 1]or[mid + 1, right]Because themidIt’s been searched. We need to rule it out
- Like theright = midorleft = midIs the way to divide an array into two intervals
Q3: How do I change the code if right = array.length and while (left < right)?
- How can we get the right result when the conditions of the right and while loops are modified, with the emphasis on exiting the loop analysis
- Under this condition, there are two cases of derivation cycle:
  - Find the target value, which is passedarray[mid] == targetConditions directlyreturn mid
  - If no target value is found, it must passleft = rightTo exit the loop, note the case of exit loop analysis:
    - At this timeleft = rightThe “search interval” when exiting the loop is[left, left)Is not to judgearray[left]Is equal to Target, so you need to add a judgment
    - At this timeleft = rightIt is possible to equal array.length, so we need to determine if the array is out of bounds
- The complete code is in transformation of Code 2
Q3: What are the flaws of this algorithm?
- Let’s say I give you an ordered array,2,2,2,3 nums = [1], target is 2, the index returned by this algorithm is 2, yes
- But if I want the left edge of target, which is index 1, or I want the right edge of target, which is index 3, then this algorithm can’t handle it
- This is very common in real development, so how to modify the above algorithm to get the left or right edge? See below
Deformation code 1

public int binarySearch(int[] array, 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;  // Notice that something has changed here, too}}return nums[left] == target ? left : -1;
}
Copy the code

Deformation Code 2

public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length;

    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;  // 后面会讲为什么是 mid 而不是 mid - 1}}if(left == nums.length || nums[left] ! = target)return -1;
    return left;
}
Copy the code

Find the left boundary

Search for a number in an array with duplicate numbers, returning the leftmost subscript if it exists, and -1 if it does not

public int leftBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length;  // Note the comparison with the next version

    while(left < right) {  // Note the comparison with the next version
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            right = mid;  // Note the comparison with the next version
        }
        else if (nums[mid] < target) {
            left = mid + 1;
        }
        else if (nums[mid] > target) {
            right = mid;  // Note the comparison with the next version}}if(left == nums.length || nums[left] ! = target)return -1;
    return left; 
}
Copy the code

Q1: Why is it written hereright = nums.lengthSo that the search interval becomes left closed and right open?
- This is common for binary searches that search the left and right edges
- It’s also provided laterright = nums.length - 1, and use this way, need to pay attention to the changes
Q2: Why is it in while<Rather than< =?
- becauseright = nums.lengthRather thannums.length - 1. So the search interval for each cycle is[left, right)Left closed right open form
- In this case, it is throughleft = rightTo exit the loop, note the case of exit loop analysis:
  - At this timeleft = rightThere is no judgment when exiting the looparray[left]Is equal to Target, so you need to determine
  - At this timeleft = rightIt is possible to equal array.length, so we need to determine if the array is out of bounds
Q4: Whyleft = mid + 1.right = mid? It’s different from the previous algorithm, right?
- Because our search interval is[left, right)Left closed right open, so whennums[mid]After being detected, the next search interval should be divided into two intervals without mid, namely[left, mid) 或 [mid + 1, right)
Q3: Why can this algorithm search the left edge?
- The point is thatnums[mid] == targetHandling of this situation:if (nums[mid] == target) right = mid;
- Instead of immediately returning to target, narrow the upper bound of the “search range” right, in the range[left, mid) Continue to search, that is, constantly left shrinkage, to achieve the purpose of locking the left boundary
Q5: Can you make itright = nums.length - 1That is, to continue to use the “search interval” with both sides closed?
- If you want to makeright = nums.length - 1, then we need to change the while statement to:while (left <= right)
- The logic for updating left and right needs to be modified
```
if (nums[mid] == target) {
    right = mid - 1;  // Shrink the right edge
}
else if (nums[mid] < target) {
    left = mid + 1;  // Search interval changed to [mid+1, right]
}
else if (nums[mid] > target) {
    right = mid - 1;  // Search interval changed to [left, mid-1]
}
Copy the code
```
- In this case, it is throughleft = right + 1To exit the loop, note the case of exit loop analysis:
  - At this timeleft = right + 1Exit the loop without judgingarray[left]Is equal to Target, so you need to determine
  - whentarget 比 numsWill exist if all elements inleft = right + 1 = nums.lengthMakes the index out of bounds, so you need to add a judgment at the end
- The complete code is morphing code 1
Deformation code 1

public int leftBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;  // Note the comparison with the previous version

    while(left <= right) {  // Note the comparison with the previous version
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            right = mid - 1;  // Note the comparison with the previous version
        }
        else if (nums[mid] < target) {
            left = mid + 1;
        }
        else if (nums[mid] > target) {
            right = mid - 1;  // Note the comparison with the previous version}}if(left == nums.length || nums[left] ! = target)return -1;
    return left;
}
Copy the code

Look for the right boundary

Search for a number in an array with duplicate numbers, returning the right-most subscript if it exists, or -1 if it does not

public int rightBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length;  // Note the comparison with the next version
    
    while(left < right) {  // Note the comparison with the next version
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return left = mid + 1;  // Note the comparison with the next version
        }
        else if (nums[mid] < target) {
            left = mid + 1;  // Note the comparison with the next version
        }
        else if (nums[mid] > target) {
            right = mid  // Note the comparison with the next version}}if (left == 0 || nums[left - 1] != target ) return -1;
    return left - 1;  // The return value is -1
}
Copy the code

Q1: Why is it written hereright = nums.lengthSo that the search interval becomes left closed and right open?
- I’ve solved it up here
Q2: Why is it in while<Rather than< =?
- I’ve solved it up here
Q3: Why can this algorithm search the right edge?
- The point is thatnums[mid] == targetProcessing:if (nums[mid] == target) left = mid + 1;
- whennums[mid] == targetDo not return immediately, but increase the lower bound left of the “search interval”, so that the interval continuously shrinks to the right, to achieve the purpose of locking the right boundary
Q4: Why is it finally returnedleft - 1Unlike the function on the left margin, returnsleft? And I think since we’re searching the right-hand side, we should go backrightto
- First of all, one of the conditions for exiting the loop isleft == right, then returnright - 1And returnleft - 1Is the same
- Again, why returnleft - 1Rather thanleft?
  - Again, the key point isif (nums[mid] == target) return left = mid + 1;Because when it’s equalleftI added 1 first, so when I returnmidWhen I subscript theta,leftOf course, we need to subtract 1 and return:mid = left - 1
Q5: Can you make itright = nums.length - 1That is, to continue to use the “search interval” with both sides closed?
- If you want to makeright = nums.length - 1, then we need to change the while statement to:while (left <= right)
- The logic for updating left and right needs to be modified
```
if (nums[mid] == target) {
    left = mid + 1;  // Shrink the left edge
}
else if (nums[mid] < target) {
    left = mid + 1;  // Search interval changed to [mid + 1, right]
}
else if (nums[mid] > target) {
    right = mid - 1;  // Search interval changed to [left, mid-1]
}
Copy the code
```
- In this case, it is throughleft = right + 1To exit the loop, note the case of exit loop analysis:
  - At this timeleft = right + 1Exit the loop without judgingarray[right]Is equal to Target, so you need to determine
  - whentarget 比 numsWhen all the elements are small, it will existright = left - 1 = -1Makes the index out of bounds, so you need to add a judgment at the end
- The complete code is morphing code 1
Deformation code 1

public int rightBound2(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;  // Note the comparison with the previous version

    while(left <= right) {  // Note the comparison with the previous version
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            left = mid + 1;
        }
        else if (nums[mid] < target) {
            left = mid + 1;
        }
        else if (nums[mid] > target) {
            right = mid - 1;  // Note the comparison with the previous version}}if (right < 0|| nums[right] ! = target )return -1;
    return right;  // Note the comparison with the previous version
}
Copy the code

Summary (Logical unity)

Find a number I

If initialize: right = nums.length thenwhileThe conditions of the cycle are:while(left < right) then left and right update logic is:if (nums[mid] == target) return mid;
    else if (nums[mid] < target) left = mid + 1;
    else if(nums[mid] > target) right = mid; Finally, you need to judge before returning:if(left == nums.length || nums[left] ! = target)return -1;
    return left;
Copy the code

public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length;

    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;  // 后面会讲为什么是 mid 而不是 mid - 1}}if(left == nums.length || nums[left] ! = target)return -1;
    return left;
}
Copy the code

Find the left boundary ⅰ

If initialize: right = nums.length thenwhileThe conditions of the cycle are:while(left < right) then left and right update logic is:if (nums[mid] == target) right = mid;
    else if (nums[mid] < target) left = mid + 1;
    else if(nums[mid] > target) right = mid; Finally, we need to judge and return:if(left == nums.length || nums[left] ! = target)return -1;
    return left;
Copy the code

public int leftBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length;  // Note the comparison with the next version

    while(left < right) {  // Note the comparison with the next version
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            right = mid;  // Note the comparison with the next version
        }
        else if (nums[mid] < target) {
            left = mid + 1;
        }
        else if (nums[mid] > target) {
            right = mid;  // Note the comparison with the next version}}if(left == nums.length || nums[left] ! = target)return -1;
    return left; 
}
Copy the code

Finding the right boundary ⅰ

If initialize: right = nums.length thenwhileThe conditions of the cycle are:while(left < right) then left and right update logic is:if (nums[mid] == target) left = mid + 1;
    else if (nums[mid] < target) left = mid + 1;
    else if(nums[mid] > target) right = mid; Finally, we need to judge and return:if (left == 0 || nums[left - 1] != target) return -1;
    return left - 1;
Copy the code

public int rightBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length;  // Note the comparison with the next version
    
    while(left < right) {  // Note the comparison with the next version
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return left = mid + 1;  // Note the comparison with the next version
        }
        else if (nums[mid] < target) {
            left = mid + 1;  // Note the comparison with the next version
        }
        else if (nums[mid] > target) {
            right = mid  // Note the comparison with the next version}}if (left == 0 || nums[left - 1] != target ) return -1;
    return left - 1;  // The return value is -1
}
Copy the code

Find a number ⅱ

If initialized: right = nums.length -1thenwhileThe conditions of the cycle are:while(left <= right)if (nums[mid] == target) return mid;
    else if (nums[mid] < target) left = mid + 1;
    else if (nums[mid] > target) right = mid - 1; Finally, we can return directly:return -1;
Copy the code

public int binarySearch(int[] array, int target) {
    int left = 0;
    int right = array.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (array[mid] == target) {
            return mid;
        } else if (array[mid] < target) {
            left = mid + 1;
        } else if (array[mid] > target) {
            right = mid - 1; }}return - 1;
}
Copy the code

Find the left boundary ⅱ

If initialized: right = nums.length -1thenwhileThe conditions of the cycle are:while(left <= right)if (nums[mid] == target) right = mid - 1;
    else if (nums[mid] < target) left = mid + 1;
    else if (nums[mid] > target) right = mid - 1; Finally, we need to judge and return:if(left == nums.length || nums[left] ! = target)return -1;
    return left;
Copy the code

public int leftBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;  // Note the comparison with the previous version

    while(left <= right) {  // Note the comparison with the previous version
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            right = mid - 1;  // Note the comparison with the previous version
        }
        else if (nums[mid] < target) {
            left = mid + 1;
        }
        else if (nums[mid] > target) {
            right = mid - 1;  // Note the comparison with the previous version}}if(left == nums.length || nums[left] ! = target)return -1;
    return left;
}
Copy the code

Find the right boundary ⅱ

If initialized: right = nums.length -1thenwhileThe conditions of the cycle are:while(left <= right)if (nums[mid] == target) left = mid + 1;
    else if (nums[mid] < target) left = mid + 1;
    else if (nums[mid] > target) right = mid - 1; Finally, we need to judge and return:if (right < 0|| nums[right] ! = target)return -1;
    return right;
Copy the code

public int rightBound2(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;  // Note the comparison with the previous version

    while(left <= right) {  // Note the comparison with the previous version
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            left = mid + 1;
        }
        else if (nums[mid] < target) {
            left = mid + 1;
        }
        else if (nums[mid] > target) {
            right = mid - 1;  // Note the comparison with the previous version}}if (right < 0|| nums[right] ! = target )return -1;
    return right;  // Note the comparison with the previous version
}
Copy the code

LeetCode related questions

Binary search
35. Search for insertion locations
34. Find the first and last positions of elements in a sorted array

Reference and thanks

Dichotomous search details, incidentally compose a poem

Writing in the front

The basic framework

Find a number

Find the left boundary

Look for the right boundary

Summary (Logical unity)

Find a number I

Find the left boundary ⅰ

Finding the right boundary ⅰ

Find a number ⅱ

Find the left boundary ⅱ

Find the right boundary ⅱ

LeetCode related questions

Reference and thanks

Related Posts

ThreadLocal for concurrent programming

DDoS attacks reported in the first half of 2018: Peak traffic of 1.7Tbps

MySQL > Interview questions, select sample questions + picture analysis + answer sharing