Binary thinking is very simple, but it is hard to understand the details of the code, every time do algorithm in binary variant, mind is paste, understand at the time, but forget, need to pay attention to the details of the too much too much, there are many online analysis of binary variant’s blog, write very detailed, but always after reading…

Today happened to encounter this kind of algorithm, think over the pain, must solve this problem. Therefore, I analyzed the idea of dichotomy in detail, and the feeling suddenly became clear. Here I share the solution that I think is the easiest to understand:

To write the correct dichotomy, you must understand the following:

  1. In The Java language, the division results are directly truncated integers, such as (2+1)/2=1, which means that it is tilted to the left in the binary, and you need to understand this to figure out where mid is at the end.

  2. Because it’s binary search, so you don’t have to know exactly what the contraction conditions are on both sides, you can do it by elimination, as long as you can make it clear that the value must not be on this side, then the value must be on the other side.

  3. BinarySearch () : (left+right)/2: (left+right)>>>1: (Left +right)/2: (left+right)/2: (left+right) For example, -1>>>1 results in integer.max_value, which is no longer divided by 2. So it’s better to use right plus left-right over 2 instead

  4. You need to understand that if there is no target in the array, then the final position of mid,left, and right should be where.

    The pseudocode is as follows:

    while(left<=right){
    ...
    mid=(left+right)/2;    
}
Copy the code

    Left >right, mid=(left+right)/2

    In other words, if the array [2,3,4,6,7,8,9] is looking for 5, then eventually left will point to the number less than 5 in the array, which is 4, index is 2, right will point to the number more than 5, which is 6,index is 3. According to dichotomy, mid should point to the middle between 4 and 5. That is, if 5 exists, 5 should exist, but since the first mid is tilted to the left, mid will point to 4 and index will be 2.

Understand the above truth, you can run dichotomy and all kinds of dichotomy variant.

The standard binary

The standard dichotomy goes without saying.

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

Duplicate data exists. Look for the coordinates that first appear

Standard binary can find the data, but sometimes we need to find the location of the first target, for example:

[1,2,2,2,3,3,4,5,6] target=2

If you do a standard binary search, it will return directly on the second half, but that’s not where it happened the first time.

If target is not included in the array, mid will be left of mid and left of mid.

As shown in the figure above, with this feature, we can solve the above problem. Although the number may be repeated, as long as we keep shrinking to the left even after finding the specific value, the final position of the pointer must be at the current maximum position less than target.

As shown in the figure above, we find target as 5, but after we find 5, we continue to process target as 5>target. At this point, the interval will continue to shrink to the left, and eventually the pointer will stay at 4. At this point, we return mid+1.

The code is as follows:

public int binarySearchFirst(int[] nums,int target){
    int left=0;
    int right = nums.length-1;
    int mid = right + (left - right)/2;
    while(left<=right){
        // Find the specific value, continue to the left shrink
        if(nums[mid]==target){
            right=mid-1;
        }else if(nums[mid] < target){
            left = mid +1;
        }else{
            right = mid -1;
        }

        mid = right + (left - right)/2;
    }
    If target is larger than all elements in the array, mid=nums.length-1, mid+1 will be out of bounds
    if(mid==nums.length-1) {return -1;
    }
    // If mid+1 is target, it does not exist in the array
    return nums[mid+1]==target? mid+1: -1;

}
Copy the code

Duplicate data exists. Look for coordinates last seen

If there is duplicate data, return the coordinates of the last occurrence. Such as:

[1,2,2,2,3,3,4,5,6] target=2

In fact, once you understand the above principle, I think the code should be written pretty quickly. When we find 5, make 5 greater than target, so that the pointer continues to shrink to the left. When we need to find the last coordinate that appears, we should move closer to 6. At this point, we only need to make 5 less than target, so that the pointer shrinks to the right.

If nums[mid]==target, do the same as if nums[mid]

The code is as follows:

public int binarySearchLast(int[] nums,int target){
    int left=0;
    int right = nums.length-1;
    int mid = right + (left - right)/2;
    while(left<=right){
        // Find the specific value, continue to the right of the contraction
        if(nums[mid]==target){
            left = mid +1;
        }else if(nums[mid] < target){
            left = mid +1;
        }else{
            right = mid -1;
        }

        mid = right + (left - right)/2;
    }
    If target is smaller than all the elements in the array, mid=-1, nums[mid] will be out of bounds
    if(mid==-1) {return -1;
    }
    If mid is target, the element does not exist in the array
    returnnums[mid]==target? mid:-1;
}
Copy the code

Partially ordered binary search

There’s a problem in LeetCode that says, look for a rotated array, an ordered array, rotated to form a new array, and you need to look for a value in that array.

For example: [4,5,6,7,1,2,3] or [8,1,2,3,4,5,6,7]

In fact, the answer to this question is simply to remember the second dichotomy mentioned at the beginning:

Because it’s binary search, so you don’t have to know exactly what the contraction conditions are on both sides, you can do it by elimination, as long as you can make it clear that the value must not be on this side, then the value must be on the other side.

Nums [mid] = nums[mid] = nums[mid] = nums[mid] = nums[mid] = nums[mid] = nums

conclusion

There are many variations of dichotomy, but they are all the same. It is important to understand where the coordinates of the three key positions are if the dichotomy runs all the way to the end of the Whlie condition, and the properties of these three coordinates will solve most of the problem.