【LeetCode】35、搜索插入位置

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 <= 10^4
-10^4 <= nums[i] <= 10^4
nums 为 无重复元素 的 升序 排列数组
-10^4 <= target <= 10^4

解题思路：

大家注意这道题目的前提是数组是有序数组，这也是使用二分查找的基础条件。

以后大家 只要看到题里给出的数组是有序数组，都可以想一想是否可以使用二分法。

同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下表可能不是唯一的。

分别处理如下四种情况：

    // 目标值在数组所有元素之前  [0, -1]
    // 目标值等于数组中某一个元素  return mid;
    // 目标值插入数组中的位置 [left, right]，return  right + 1
    // 目标值在数组所有元素之后的情况 [left, right]，这是右闭区间，所以  return left

参考代码：

class Solution {
    
    public int searchInsert(int[] nums, int target) {
    
        int right = nums.length-1;
        int left = 0;

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

} 

总结

希望通过这道题目，大家会发现平时写二分法，为什么总写不好，就是因为对区间定义不清楚。

确定要查找的区间到底是左闭右开[left, right)，还是左闭又闭[left, right]，这就是不变量。

然后在二分查找的循环中，坚持循环不变量的原则，很多细节问题，自然会知道如何处理了。