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