原文链接: https://leetcode-cn.com/problems/N6YdxV

中文题目

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

请必须使用时间复杂度为 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

示例 4:

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

示例 5:

输入: nums = [1], target = 0
输出: 0

 

提示:

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

 

注意：本题与主站 35 题相同： https://leetcode-cn.com/problems/search-insert-position/

通过代码

高赞题解

二分查找

这道题就是标准二分查找的一个变型，代码比较简单，主要说明两点：

1. mid = left + ((right - left) >> 1) 的写法比 mid = (left + right) / 2 好，因为 left + right 可能会溢出，同时位运算的效率更高；
2. 当出现 nums[mid] >= target 的情况，还需要加一个判断 mid == 0 || nums[mid - 1] < target，若成立则说明，前一个数比 target 小，那么就找到了位置。若在 while 循环内都未找到符合要求的位置，那么说明 target 比所有的数都要大，需要插入到数组的最后一个数字之后，即返回 nums.size()。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] >= target) {
                if (mid == 0 || nums[mid - 1] < target) {
                    return mid;
                }
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        return nums.size();
    }
};

提供一下二分查找的标准模板，不建议用递归的形式实现，用迭代比较好。

int left = 0;
int right = nums.size() - 1;
while (left <= right) {
    int mid = left + ((right - left) >> 1);
    if (nums[mid] == target) {
        return mid;
    }
    nums[mid] > target ? right = mid - 1 : left = mid + 1;
}
return -1;

统计信息

通过次数	提交次数	AC比率
4617	9174	50.3%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言