Leecode 搜索插入位置

Day 2 刷题

1. 我的思路：利用二分法解决问题，不过由于情况没有好好分类，以及循环判定条件不合适，会出现超出运行时间的bug。

class Solution {
    public int searchInsert(int[] nums, int target) {
        int length = nums.length;
        int StartIdx = 0;
        int FinalIdx = length-1;
        int TargetIdx;
        int MiddleIdx = StartIdx + (FinalIdx-StartIdx)/2;
        // default is flooring
        while(MiddleIdx!=StartIdx){            
            int MiddleVal = nums[MiddleIdx];
            if(MiddleVal > target){      
               FinalIdx = MiddleIdx-1;
            }
            else if(MiddleVal < target){             
                StartIdx = MiddleIdx+1;
            }
            else{
                return MiddleIdx;
            }  
            MiddleIdx = StartIdx + (FinalIdx-StartIdx)/2;          
        }
        if (nums[StartIdx]<target && nums[FinalIdx]>=target){
            TargetIdx = FinalIdx;
        }
        else if(nums[FinalIdx]<target){
            return (FinalIdx+1);
        }   
        else{
            return StartIdx;
        }    
        return TargetIdx;       
    }

}

2. 力扣官方题解：官方的怎么处理target值等于mid时候值的需要好好学习，呜呜！一直都搞不出来

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

关于插入的元素可能在数组的两端的问题，巧妙地利用

int ans = nums.length插入的元素target比数组中所有元素大;

mid>=target插入的元素target比数组中所有元素小。