Recently in the binary search algorithm, found that binary search is not as simple as imagined, especially the termination condition, has mid value problem, always let me confused, the following with an example, say my understanding of binary search induction:

Leetcode: Sword refers to Offer 53-i. Looks for the number I in the sorted array

Count the number of occurrences of a number in a sorted array.

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8 output: 2Copy the code

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6 output: 0Copy the code

Limitations:

0 <= Array length <= 50000Copy the code

Source: LeetCode link: leetcode-cn.com/problems/za… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

I believe that you have understood the meaning of this topic: let me say that I was doing this topic train of thought

Thinking a

Select * from target; select * from target; select * from target;

public int search(int[] nums, int target) {
        int index = getIndex(nums,target);
        if(index < 0) {return 0;
        }
        int count = 1;
        // There may be more on the left
        for(int i = index-1 ; i >= 0; i--){
            if(nums[i] ! = target){break;
            }
            count++;
        }
        // There may also be one on the right
        for(int i = index+1; i < nums.length; i++){
            if(nums[i] ! = target){break;
            }
            count++;
        }
        return count;
    }

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

Execution Result:

Results: Beat 100.00% user memory consumption in all Java commits: 41.5 MB and beat 27.56% user memory in all Java commits with execution time: 0 msCopy the code

Of course, we’re not talking about performance efficiency or memory consumption here, we’re just trying to generalize some of the areas of binary lookup that often confuse us. Here we focus on the getIndex method: this method can be summarized as: find the target in the array, return index, return -1

Array values found

Question (1) : When does the code terminate?

We define left=0,right=length-1, so our search scope is [left, right], closed interval, and if we set left < right then the termination condition is left= = right, [right, right], missing an int[right] or int[left], If we set it to left <= right, then the termination condition is left == right+1, and the [right+1, right] range is null

Int mid = (right+left)/2 +left)/2

The main consideration is integer overflow, which we won’t focus on here (and don’t need to, haha).

Question (3) Why is right mid – 1 and left mid + 1?

Mainly because our range is a closed interval, and we already know that mid doesn’t work;

Idea 2

Count = rightIndex-leftindex-1; For example ums = [5,7,7,8,8,10] target = 8, 4-3+1= 2

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

        left = 0;
        right = nums.length;
        // Find the right edge
        while(left < right){
            int mid = left + (right-left)/2;
            if(nums[mid] == target){
                left = mid + 1;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else{ right = mid; }}int rightindex = right - 1;

        int count = rightindex - leftindex + 1;
        return count;
        
    }
Copy the code

Execution Result:

Execution time:0Ms, beat out all Java commits100.00% user memory consumption:41.1MB, beat out all Java commits90.76% of the userCopy the code

Find the left edge:

Question 1: Why is the end condition left < right

Left =0, right=length, [left,right =length] Left == right+1 left= = right+1 left= = right+1 left= = right+1 left= = right+1

Question 2: Why is the last left boundary left

Left ==right; nums[mid]=target

Look for the right edge

Nums [mid] == target, left == mid + 1; nums[mid] == target, left == mid + 1; So mid == left-1, right-1;

conclusion

When writing the binary search, we should first understand the opening of the interval, then exit conditions are determined according to the open and close, of course whether it is left on the right or left closed off right away, we can replace for the closed interval, the final return data to the corresponding relationship with mid to so in the face of binary search, we would never return to exit conditions and parameters and melancholy.