二分查找应用1
2021-09-19 / ryanxw

题目

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

  • 要求：时间复杂度为 O(log n)
  • 例子：
    • 输入: nums = [1,3,5,6], target = 5 输出: 2
    • 输入: nums = [1,3,5,6], target = 2 输出: 1
  • leetcode链接

    解法：改写二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int searchInsert(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    int mid = 0;
    bool flag = false;
    int ans = 0;
    while (left <= right) {
        mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            flag = true;
            ans = mid;
            break;
        }
        else if (nums[mid] < target) {
            left = mid + 1;
        }
        else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    if (!flag) {
        if (nums[mid] > target) { // 用于判断左边界 比如[1,3,5,6] target=0
            ans = mid;
        }
        else {
            ans = mid + 1;
        }
    }
    return ans;
}