LeetCode——搜索插入位置

NO.35 搜索插入位置 简单

思路一：暴力法 线性查找，找到目标值或者大于目标值元素则停止。否则插入到返回nums.length。

public int searchInsert(int[] nums, int target) {    
    for(int i=0;i<nums.length;i++){        
        if (nums[i]==target||nums[i]>target)return i;    
    }    
    return nums.length;
}

时间复杂度:O(n)

思路二：二分法 和普通的二分法变化不大,主要区别在于最后查找失败后不返回-1，而是返回left。

例[1,3,5,6]、target=4。初始化left=0、right=4-1；第一次循环4>3，left=1+1；第二次循环4<5，right=2-1；left>right循环结束，返回left，即插入位置为2。

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

需要注意right的初始取值，会影响搜索区间继而影响循环终止条件、right移动。

时间复杂度：O(logn)

---

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github