35.搜索插入位置
题目：搜索插入位置
自己尝试了好几种写法：
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r)
{
int mid = l + (r - l) / 2;
if (nums[mid] > target) r = mid - 1;
else if (nums[mid] < target) l = mid + 1;
else return mid;
}
return l;
}
};
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r)
{
int mid = l + (r - l) / 2;
if (nums[mid] > target) r = mid - 1;
else if (nums[mid] < target) l = mid + 1;
else return mid;
}
return r + 1;
}
};
// 相当于找到第一个大于等于target的位置，二分法是无限逼近这个数的位置（因为这个数有可能不存在）
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int n = nums.size();
if (n == 1 && nums[0] >= target) return 0;
int l = 0, r = n - 1;
while (l < r)
{
int mid = l + (r - l) / 2;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
if (l == n - 1 && nums[l] < target) return n;
return l;
}
};
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r)
{
int mid = l + (r - l) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] > target) r = mid - 1;
else l = mid + 1;
}
return r + 1;
}
};
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r)
{
int mid = l + (r - l) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] > target) r = mid - 1;
else l = mid + 1;
}
return l;
}
};
自己最满意最后两种写法，前面的三种写法思路都不够清晰，有种误打误撞的感觉，感觉是对着正确输出改代码hh
对倒数第二种写法的精髓理解：
要注意当l==r时（即此时只有一个数据）的情况：
当l == r时，此时mid == l == r，如果nums[mid] > target，则
r = mid - 1，此时插入的位置是在r之后（即r + 1），如果nums[mid] < target，则l = mid + 1，此时插入的位置仍然是在r之后（因为nums[mid] < target相当于nums[r] < target，自然要插入到r之后，即r + 1）。
然后最后一种写法也可以按照上述那样取特殊情况理解，此处不赘述。
总结一下：
倒数第二种写法（返回r + 1的那种），其实r找的是最后一个小于target的位置，自然插入的时候要在r+1位置插入。
最后一种写法（返回l的那种），其实l找的是第一个大于target的位置，自然插入的时候在l位置插入就OK了。
注意：
上述分析过程都仅限于数组没有重复元素前提下。