问题

• 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
  请必须使用时间复杂度为 O(log n) 的算法。

解决

// 排序数组
// 目标值
// 返回位置，或者被插入位置
//请必须使用时间复杂度为 O(log n) 的算法。
//暴力解法
class Solution {
    public int searchInsert(int[] nums, int target) {
        int n=nums.length;          //获取nums数组长度
        if(target<=nums[0]) return 0;       //当目标数字与数组第一个数字相等时，直接返回0
        for(int i=0;i<n-1;i++){             //当目标数字在（或者需要插入）数组中位置0<target<=n-1之间时，返回位置
            if(nums[i]<target&&nums[i+1]>=target){
                return i+1;
            }
        }
        return n;           //当目标数字大于最后一个数字时，返回数组长度n
    }
}



//二分算法，利用中间值进行比较，目标值比中间值大则left向右移动，比中间值小则right向右移动。
class Solution{
    public int searchInsert(int nums[],int target){
        int left=0,right=nums.length-1;
        int mid=0;
        for(;left<=right;){             //left应该是小于等于right
            mid=(left+right)/2;
            if(nums[mid]==target) return mid;
            else if(target<nums[mid]) right=mid-1;
            else left=mid+1;          
        }
        return left;
    }
}

总结

• 两种算法复杂度都是