35. search insertion position

35. Search insert location

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 <= 104
-104 <= nums[i] <= 104
nums by No repeating elements Of Ascending Arrange arrays
-104 <= target <= 104

Their thinking ：

• Solve with dichotomy
• First set the left subscript left And right subscript right, Then calculate the middle subscript mid
• Per basis nums[mid] and target Judge the size between , Equal returns the subscript directly ,
• nums[mid] < target be left Move right ,
• nums[mid] > target be right Move left
• End of search. If there is no equal value, return left, This value is the insertion position

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

Reference resources ：LeetCode