LeetCode-35-Search Insert Position-E

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

Input: [1,3,5,6], 5

Output: 2

Example 2:

Input: [1,3,5,6], 2

Output: 1

Example 3:

Input: [1,3,5,6], 7

Output: 4

Example 4:

Input: [1,3,5,6], 0

Output: 0

最容易想到的一般解法

int searchInsert(vector<int>& nums, int target) {
        for(int i=;i<nums.size();i++){
            if(target<=nums[i])
                return i;
        }
        return nums.size();
    }
           

二分查找

時間複雜度為logn

int searchInsert(vector<int>& nums, int target) {
        int low=,high=nums.size()-,mid;
        while(low<=high){
            mid=low+(high-low)/;
            if(nums[mid]<target)
                low=mid+;
            else 
                high=mid-;
        }
        return low;
    }
           

補充一下對于這個經典的二分查找算法的解釋：

知乎-二分查找有幾種寫法？它們的差別是什麼？