35. 搜索插入位置 - 力扣（LeetCode）

发表于 更新于 分类于 阅读次数： Disqus：

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 你可以假设数组中无重复元素。 示例 1: 输入: [1,3,5,6], 5 输出: 2 示例 2: 输入: [1,3,5,6], 2 输出: 1 示例 3: 输入: [1,3,5,6], 7 输出: 4 示例 4: 输入: [1,3,5,6], 0 输出: 0

题解

二分法查找，不用多说，具体见代码

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int beg = 0, end = nums.size() - 1;
        int mid = (beg + end) / 2;
        while(beg <= end){//二分查找法
            mid = (beg + end ) / 2;
            if(nums[mid] > target){
                end = mid - 1;
            }
            else if(nums[mid] < target){
                beg = mid + 1;
            }
            else{
                return mid;
            }
        }
        return beg;
    }
};

执行结果

优化

将mid=(beg+end) / 2改成位移运算，运算效率会高得多。另外看到一篇题解,发现自己写的二分查找还是存在许多问题，比如，这次我就在返回beg还是end犹豫了一下，虽然凭直觉选对了，但还是把循环条件改成beg < end来得好。有时间要抽空看看那篇题解，应该会受益匪浅。

执行结果