The binary search boundary value processing based on leetcode35 is used to clarify the boundary value of the judgment condition using the idea of interval

Binary search ideas

Reprint , For self review and review
The idea of this article is very good , be used for Clarify the boundary value processing
be based on leetcode35
The subject , To insert the target value into the array , These are the four situations .

The target value precedes all elements of the array
The target value is equal to an element in the array
The position where the target value is inserted into the array
The target value is after all elements of the array

These four conditions have been confirmed , You can try to solve the problem .

Next, I will explain this problem from the solution of violence and dichotomy , Let's also talk about the binary search method .

Violence solution

Violent problem solving Not necessarily, the time consumption is very high , The key depends on the way of implementation , Like binary search, the time consumption is not necessarily very low , It's the same .

Violence solution C++ Code

class Solution {
    
public:
    int searchInsert(vector<int>& nums, int target) {
    
        for (int i = 0; i < nums.size(); i++) {
    
        //  Deal with the following three situations respectively 
        //  The target value precedes all elements of the array 
        //  The target value is equal to an element in the array 
        //  The position where the target value is inserted into the array 
            if (nums[i] >= target) {
     //  Once found to be greater than or equal to target Of num[i], that i It's what we want 
                return i;
            }
        }
        //  Where the target value is after all elements of the array 
        return nums.size(); //  If target It's the biggest , perhaps  nums It's empty , Then return to nums The length of 
    }
};

Time complexity ：O(n)
Spatial complexity ：O(1)

Dichotomy

Since the time complexity of the brute force solution is O(n), Just try using binary search .

The premise of this topic is that the array is an ordered array , This is also the basic condition of using binary search .

After that, everyone As long as you see that the array given in the interview question is an ordered array , Think about whether you can use dichotomy .

At the same time, the title also emphasizes that there are no duplicate elements in the array , Because once there's a repeating element , The element subscript returned by binary search method may not be unique .

Binary search involves many boundary conditions , The logic is simple , It's just that it can't be written well .

I believe many students do not handle the boundary conditions well in the binary search method .

For example, what is it while(left < right) still while(left <= right), What is the right = middle Well , Still right = middle - 1 Well ？

It's not clear here mainly because The definition of interval is not clear , This is the invariant .

In the process of binary search , Keep invariants , This is the loop invariant （ Interested students can check ）.

Dichotomy the first way to write

Take this topic as an example , The following code defines target It's in an interval that's left closed and right closed , That is to say [left, right] （ This is very important ）.

This determines how the dichotomy code is written , Here's the code ：

You should read the notes carefully , Think about why you write while(left <= right), Why write right = middle - 1.

class Solution {
    
public:
    int searchInsert(vector<int>& nums, int target) {
    
        int n = nums.size();
        int left = 0;
        int right = n - 1; //  Definition target In a left closed right closed interval ,[left, right]
        while (left <= right) {
     //  When left==right, Section [left, right] Is still valid 
            int middle = left + ((right - left) / 2);//  Prevent overflow   Equate to (left + right)/2
            if (nums[middle] > target) {
    
                right = middle - 1; // target  In the left range , therefore [left, middle - 1]
            } else if (nums[middle] < target) {
    
                left = middle + 1; // target  In the right range , therefore [middle + 1, right]
            } else {
     // nums[middle] == target
                return middle;
            }
        }
        //  Deal with the following four situations respectively 
        //  The target value precedes all elements of the array  [0, -1]
        //  The target value is equal to an element in the array  return middle;
        //  The position where the target value is inserted into the array  [left, right],return right + 1
        //  Where the target value is after all elements of the array  [left, right], This is a right closed interval , therefore  return right + 1
        return right + 1;
    }
};

Time complexity ：O(logn)
Time complexity ：O(1)

Dichotomy the second way to write

If the definition target It's in a zone that's closed on the left and open on the right , That is to say [left, right) .

The boundary treatment of dichotomy is quite different .

The invariant is [left, right) The range of , The following code shows how invariants are persisted in loops .

You should read the notes carefully , Think about why you write while (left < right), Why write right = middle.

class Solution {
    
public:
    int searchInsert(vector<int>& nums, int target) {
    
        int n = nums.size();
        int left = 0;
        int right = n; //  Definition target In the interval between left closed and right open ,[left, right) target
        while (left < right) {
     //  because left == right When , stay [left, right) It's invalid space 
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
    
                right = middle; // target  In the left range , stay [left, middle) in 
            } else if (nums[middle] < target) {
    
                left = middle + 1; // target  In the right range , stay  [middle+1, right) in 
            } else {
     // nums[middle] == target
                return middle; //  When the target value is found in the array , Return the subscript directly 
            }
        }
        //  Deal with the following four situations respectively 
        //  The target value precedes all elements of the array  [0,0)
        //  The target value is equal to an element in the array  return middle
        //  The position where the target value is inserted into the array  [left, right) ,return right  that will do 
        //  Where the target value is after all elements of the array  [left, right), This is the right opening section ,return right  that will do 
        return right;
    }
};

Time complexity ：O(logn) Time complexity ：O(1)

summary

I hope that through this topic , You will find that you usually write dichotomy , Why can't you write well , Because the definition of interval is not clear .

Determine whether the interval to be searched is left closed and right open [left, right), Still left closed and closed [left, right], This is the invariant .

And then in In the loop of binary search , Adhere to the principle of loop invariants , A lot of details , Naturally, you will know how to deal with .

above , It's my personal records , in my opinion , The truth is infinite , Infinite progress ！

I'm a chestnut , I wish you happiness .