【二分查找】Leetcode 搜索插入位置

题目解析

35. 搜索插入位置

这道题就是寻找target的目标位置，如果nums中包含target直接返回索引；如果不包含，需要返回target存放的合适位置

注意这道题有一个细节地方需要注意：如果现在target没有在nums中出现，并且目前的target是nums中最大的那一个，此时我们使用的二分算法只能够寻找到数组的最后一个索引位置。因此，需要我们手动在最后判断一下，如果最后一个索引位置的数字 < target,那么就需要返回最后一个索引位置+1的索引位置

算法讲解

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        //最终寻找的位置是 第一个 >= target 的数字
        //我们将数组划分为两段 1. 小于target  2.大于等于target
        //也就是寻找区间的左端点
        int left = 0, right = nums.size()-1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] >= target)right = mid;
            else left = mid + 1;
        }
        //需要判断一下最后一个位置
        if(nums[left] < target)return left + 1;
        return left;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18