Search Insert Position(目标数应该插在数组中的什么位置)leetcode35

红太狼 2022-05-22 00:56 108阅读 0赞

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

Input: [1,3,5,6], 5
    Output: 2

Example 2:

Input: [1,3,5,6], 2
    Output: 1

Example 3:

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

Example 4:

Input: [1,3,5,6], 0
    Output: 0

code1：一开始的想法，想的有点多。。。。。

public int searchInsert(int[] nums, int target) {
            if(nums[0]>target)
                return 0;
            if(nums[nums.length-1]<target)
                return nums.length;
           return searchIndex(nums,0,nums.length-1,target);
        }
        int searchIndex(int[] nums,int low,int high,int target){
            
            while(low<=high){
                int middle=low+(high-low)/2;
                if(nums[middle]<target&&nums[middle+1]>target)
                    return middle+1;
                else if(nums[middle]<target)
                    low=middle+1;
                else if(nums[middle]>target&&nums[middle-1]<target)
                    return middle;
                else if(nums[middle]>target)
                    high=middle-1;
                else 
                    return middle;
                    
            }
            return -1;
        }

code2：这才是正常的操作

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