[数据结构与算法]LeetCode 35. 搜索插入位置 —vector遍历(O(logn)和O(n)的写法---二分查找法)

LeetCode 35. 搜索插入位置 —vector遍历(O(logn)和O(n)的写法—二分查找法)。

题目地址: https://leetcode.cn/problems/search-insert-position/

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

示例 1:

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

题目解法:

O(n)的写法：
一开始我的写法如下: 考虑整体遍历这个vector，然后看目标值是否小于等于这个当前值，是的话直接返回索引。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if(nums.empty()) return 1;

        const int size = nums.size();

        for (size_t i=0; i<size; ++i){
            if (target <= nums[i]) return i;
        }
        return size;
        
    }
};

但是看了题解之后，有如下写法:

O(logn)的写法：

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if(nums.empty()) return 1;

        const int size = nums.size();
        int left=0, right=size-1;

        while(left<=right){
            auto middle = left+(right-left)/2;
            if(nums[middle] <target)
                left = middle+1;
            else
                right = middle -1;
        }
        return left;
    }
};

题目笔记

最上面的当然是可以得到结果，但是下面的优势在于，使用了二分查找的思想。但前提是这个数组是有序的。 前面当然是比较直观的，但是复杂度在O(n)，二分查找只需要O(logn)。