1.题目描述

在这里插入图片描述

题目原链接：search-insert-position

2.解题思路及算法

2.1 顺序查找

  • 定义变量 i ，从前到后遍历数组，当target大于等于nums[i]时则返回 i 的值
1
2
3
4
5
6
7
8
class Solution {   //顺序查找
public:
    int searchInsert(vector<int>& nums, int target) {
        int i = 0;
        for(i;i < nums.size() && target > nums[i];i++);
        return i;
    }
};

2.2 折半查找(二分查找)

  • 定义变量low、high、mid
  • high指向数组最后(high = nums.size() - 1)
  • low指向数组最前(low = 0)
  • mid = (high + low)/2，指向high和low中间
  • 循环条件(high >= low)
  • 比较nums[mid]和target，根据结果改变high和low的值，直到跳出循环，得到答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {   //折半查找
public:
    int searchInsert(vector<int>& nums, int target) {
        int high=nums.size()-1,low=0,mid;
        while(high >= low){
            mid = (high + low)/2;
            if (nums[mid] == target)
                return mid;
            if (nums[mid] > target)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return low;
    }
};