搜索插入位置

Question

   Given a sorted array of distinct integers 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.

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

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

Example 5:

Input: nums = [1], target = 0
Output: 0

Answer

思路一

  二分法查找(binary Search): 首先先确定最高位和最低位的值,因为随着low和high的位置不断变化,
所以middle的值是不断再改变的。这里用移位(>>1)代替了除法,这样不会增加运算的复杂性。
  如果目标值大于中间值,那么low就要变化;相反，如果目标值小于中间值，high就需要变化;如果目标值正好等于中间值就可以直接输出了。
时间复杂度为O(logn),具体代码如下:

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int low = 0,high = nums.size() - 1,n = nums.size();
        
        while (low <= high) {
            int middle = low + ((high - low) >> 1);
            if (target > nums[middle]) low = middle + 1;
            else if (target < nums[middle]) high = middle - 1;
            else return middle;
        }
        return low;
    }
};

思路二

  线性查找(linear search): 将nums的值挨个赋给i,如果i小于目标值,result就自增。相反如果大于等于目标值，就可以直接跳出循环，输出结果了。时间复杂度为O(n),具体代码如下:

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int result = 0;
        for (auto& i : nums) {
            if (i < target){
                result++;
            } 
            else break;
        }
        return result;
    }
};