[leetcode] 35. Search the insertion position

35、 Search insert location

subject ：

Given a sort array and a target value , Find the target value in the array , And return its index . If the target value does not exist in the array , Return to where it will be inserted in sequence .

Please use a time complexity of O(log n) The algorithm of .

Example 1：

 Input : nums = [1,3,5,6], target = 5
 Output : 2

Example 2：

 Input : nums = [1,3,5,6], target = 2
 Output : 1

Example 3：

 Input : nums = [1,3,5,6], target = 7
 Output : 4

Tips ：

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums by No repeating elements Of Ascending Arrange arrays
-10^4 <= target <= 10^4

Their thinking ：

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 Just see that the array given in the question is Ordered array , Can think about whether it can be used Dichotomy .

At the same time, the title also emphasizes that in the array No repeating elements , Because once there's a repeating element , The following table of elements returned by binary search may not be unique .

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 mid;
    //  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 left

Reference code ：

class Solution {
    
    public int searchInsert(int[] nums, int target) {
    
        int right = nums.length-1;
        int left = 0;

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

} 

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 .