关阿姨带你横扫LeetCode系列之搜索插入位置

关阿姨正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

首先跟大家阐明一点就是，每道算法题都有多种解法，我们只讲LeetCode上几种优秀的解题思路~，希望可以帮助到大家，那我们先来看下题目描述吧~

一、题目描述：

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

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

示例 1:
输入: [1,3,5,6], 5
输出: 2

示例 2:

输入: [1,3,5,6], 2
输出: 1

示例 3:

输入: [1,3,5,6], 7
输出: 4

示例 4:

输入: [1,3,5,6], 0
输出: 0

二、思路分析：

看到这道题，大家第一个反应就应该是二分查找，为什么？因为题目说到“排序数组”，在有序数组中查找一个值，用二分查找是很普遍的，时间复杂度为在 O(log n)。
具体该如何解答呢？我们来分析下：
我们假设应该插入的位置是pos（注意是位置哈），那pos成立条件为：nums[pos-1] < target <= nums[pos]
如果以上假设成立，我们返回的索引也是应该是pos，那这个问题就转化为了：在有序数组中查找第一个大于等于target的元素的索引。
说到这里，大家应该就能恍然大悟了：在有序数组中查找一个值，用二分查找。对吧。
那废话不多说，上代码看看

代码实现

public int searchInsert(int[] nums, int target) {
    int n = nums.length;
    // 左边从0开始，右边从n-1开始，ans 初值设置为数组长度
    int left = 0, right = n - 1, ans = n;
    while (left <= right) {
        // 获取中间值
        // >> 1 是位运算，相当于除以二的意思
        // 大家思考一下这里为什么是right - left除以二，然后再加left？(right+left)除以二不行吗？
        int mid = ((right - left) >> 1) + left;
        if (target <= nums[mid]) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ans;
}
复制代码