Binary search related topics, there are probably two types: one is looking for value, one is looking for scope. The general idea of binary search is quick to come up with, but the details are excruciating, such as the following:

  1. returnleftorright
  2. The right boundary isnums.lengthornums.length - 1
  3. while ( left ? right)Is to take<or< =

This article refers to the solution of LeetCode’s comment section and labuladong’s algorithm cheat sheet, and will supplement the above details and apply them to the corresponding topic.

Find a number

This is a familiar scenario, looking for a number in a sorted array, returns the index if it finds one, returns -1 if it doesn’t

public int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; / / note

    / / note that < =
    while(left <= right) { 
        int mid = left + (right - left) / 2;
        if(nums[mid] == target){
            return mid; 
        } else if (nums[mid] < target){
            left = mid + 1; / / note
        } else if (nums[mid] > target){
            right = mid - 1; / / note}}return - 1;
}
Copy the code

Analysis:

  1. rightIn the while loopleft<rightorleft<=right
  2. rightThe initialization value of right also affects that right should be updated tomid+1ormid

1. Why in the while loop< =Rather than< ？

  • Because right initializes nums.length-1, the index of the last element, which corresponds to a closed interval [left, right] where left can equal right, <= is used.

  • If right initializes nums.length, then the corresponding closed and open range [left, right], in which left cannot equal right, should use <.

In this algorithm, we use the interval where the former [left, right] ends are closed. This interval is essentially the interval for each search. When should we stop the search, we can stop the search when we find the target value, but what if we don’t find the target value, we have to terminate the while loop and return -1

While (left <= right) terminates with left=right+1, written as [right+1, right], empty, and terminating the while loop is correct. If you use while(left < right), the terminating condition is left=right, and the interval is [right, right], and the right is not iterated, then it is wrong to terminate the loop directly. If you use <, you need to do something on return:

return nums[left] == target ? left : -1;
Copy the code

2. Is right equal to mid or mid+1?

This is the second point of the above analysis:

  • whenrightInitialized tonums.length-1Represents a left closed right closed interval[left, right]In thenums[mid]After that, the next loopnums[mid]I don’t have to do that anymore. So the left-hand interval[left,mid-1]The right-hand side is 0[mid+1,right]
  • whenrightInitialized tonums.lengthRepresents a left closed and right open interval[left, right)In thenums[mid]After that, the next loopnums[mid]I don’t have to judge it anymore, but since the right-hand side is open, so the left-hand side interval[left,mid)The right-hand side is 0[mid+1,right)

Find the left boundary

First look at the template, try to list the three if, so that you can understand the three situations

public int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; / / note

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

Similarly, the while loop uses < or <= to take the absolute value of right. It just looks for templates with more common closed left and open right boundaries.

Exiting the loop left==right, so returning left or right is the same

If nums[mid] == target, right=mid; if nums[mid] == target, right=mid; if nums[mid] = target, right=mid;

1. If THAT’s what I wantright = nums.length - 1? How to write

Left == right + 1 while left == right + 1

public int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length - 1; / / note

    while (left <= right) { / / note
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            right = mid - 1; / / note
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; / / note}}// Check the outbound condition
    if(left >= nums.length || nums[left] ! = target){return -1;
    }
    return left; // Why is this left
}
Copy the code

Because the condition for exiting the loop isleft == right + 1, so whentarget 比 numsIf all the elements in the index are large, the index will be out of bounds, so to check for out of bounds, you can also determine in the first placetargetIs greater than the largest element in the array,See below

Find the right boundary

I’m going to go straight to the code, or I’m going to write it left closed right open

public int right_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;

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

Why is left-1 returned? Well, I’ll just write it down and I’ll know why, but I’ll just keep it in mind.

Right = nums. length-1

public 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) {
            // Shrink the left edge
            left = mid + 1; }}// Check if right is out of bounds for the same reason
    if (right < 0|| nums[right] ! = target)return -1;
    return right;
}
Copy the code

At this point, the binary search algorithm is over, if you do not understand can see the link at the beginning of this article (Labuladong’s algorithm cheat sheet).