题目链接

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

示例

示例1：

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

示例2：

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

提示

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

  • -10 <= target <= 10

    思路

    二分查找

    在一个有序数组中找第一个大于等于0035-搜索插入位置 - 图1的下标

    另外

    c++的STL：

    1. class Solution {
    2. public:
    3.   int searchInsert(vector<int>& nums, int target) {
    4.       return lower_bound(nums.begin(),nums.end(),target) - nums.begin();
    5.   }
    6. };

    题解

    1. class Solution {
    2.  public:
    3.   int searchInsert(vector<int>& nums, int target) {
    4.       int n = nums.size();
    5.       int left = 0, right = n - 1, mid = 0;
    6.       int ans = n;
    7.       while (left <= right) {
    8.           mid = ((right - left) >> 1) + left;
    9.           if (target < nums[mid]) {
    10.               ans = mid;
    11.               right = mid - 1;
    12.           } else if (target > nums[mid]) {
    13.               left = mid + 1;
    14.           } else {
    15.               ans = mid;
    16.               break;
    17.           }
    18.       }
    19.       return ans;
    20.   }
    21. };

    复杂度分析

  • 时间复杂度：0035-搜索插入位置 - 图2

  • 空间复杂度：0035-搜索插入位置 - 图3