LeetCode 35. Search the insertion position - vector traversal (O (logn) and O (n) - binary search)

LeetCode 35. Search insert location —vector Traverse (O(logn) and O(n) Writing — Dichotomy search ).

Title address : https://leetcode.cn/problems/search-insert-position/

Given a sort array and a target value , Find the target value in the array , And return its index . If the target value does not exist in the array , Return to where it will be inserted in sequence .

Example 1:

Input : nums = [1,3,5,6], target = 5
Output : 2

Problem solving :

O(n) Writing ：
At first, I wrote as follows : Consider traversing this as a whole vector, Then check whether the target value is less than or equal to the current value , If yes, return the index directly .

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;
        
    }
};

But after reading the solution , It's written as follows :

O(logn) Writing ：

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;
    }
};

Topic notes

Of course, the top one can get results , But the following advantages are , Using the idea of binary search . But the premise is that the array is ordered . Of course, the front is more intuitive , But the complexity is O(n), Binary search only needs O(logn).