35.搜索插入位置 - 图1

1.题目

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例：

  1. 输入: [1,3,5,6], 5
  2. 输出: 2
  4. 输入: [1,3,5,6], 2
  5. 输出: 1
  7. 输入: [1,3,5,6], 7
  8. 输出: 4
  10. 输入: [1,3,5,6], 0
  11. 输出: 0

2.思路

一眼往上去我第一思路就是暴力法，遍历整个数组，如果数组中的元素大于等于目标元素，则返回下角标，相反则直接返回数组长度（最后一位下角标）

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

当然，我们也可以使用二分法，使用二分法可以降低时间复杂度。

使用二分法，我们肯定要定义两个指针，第一个指针在数组最开始，第二个指针在数组最末尾，然后我们取中间的指针，查看该指针的值是否大于等于目标值，如果大于等于目标值，则将左指针的值赋予右指针（跳过当前指针，重新进行二分查找）；否则将该指针的数值加1赋予左指针（跳过当前指针，重新进行二分查找）

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