LeetCode-35-搜索插入位置

题目

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

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

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

示例 2:

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

示例 3:

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

提示:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 为 无重复元素 的 升序 排列数组
• -104 <= target <= 104

题解

这一题二分查找没有什么好说的，提几个要点吧：

1. 循环条件，left <= right，注意等于号；
2. 找到了直接返回下标即可；
3. 如果目标值比中间值大，说明需要往后面找，也就是让left = mid + 1；
4. 如果目标值比中间值小，说明需要往前面找，即right = mid - 1；
5. 找不到的时候，返回的结果为left，这里分情况讨论：
   • 如果target < nums[0]，这个时候left不会动，要插入的位置自然是0也就是left；
   • 如果target > nums[nums.length - 1]，这个时候left会一直动直到为nums.length，那么插入的位置自然也是left；
   • 如果对于一般的值，按上面的两个思路思考同样可以得出left为插入的值。

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