上一篇博客：LeetCode 28. 实现 strStr()（KMP、字符串）
写在前面：大家好！我是
ACfun,我的昵称来自两个单词Accepted和fun。我是一个热爱ACM的蒟蒻。最近萌生了刷LeetCode的想法，所以我打算从LeetCode简单的题目开始做起，攻陷LeetCode。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：https://ac-fun.blog.csdn.net/。非常感谢大家的支持。一起加油，冲鸭！
用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง
原题链接：LeetCode 35. 搜索插入位置
题目信息
题目描述
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例
示例 1
输入: [1,3,5,6], 5
输出: 2
示例 2
输入: [1,3,5,6], 2
输出: 1
示例 3
输入: [1,3,5,6], 7
输出: 4
示例 4
输入: [1,3,5,6], 0
输出: 0
题解
解题思路
我们可以使用 二分查找算法 来解决这个问题。我们不断的进行二分查找直到找到目标值 target ，找不到则返回第一个大于等于 target 的值的下标。因为题目给定的是一个排序数组，所以我们在开始的时候可以特判一下目标值 target 是否比数组最后一个数大，如果比最后一个数都大的话，我们直接返回数组的长度即可。即目标值 target 应该插入到数组的最后一个位置。
解题代码
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
if (nums[r] < target) return r + 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
return l;
}
};
时间复杂度
假设 n 为数组的长度。二分查找所需的时间复杂度为 O(logn)。
提交结果
二分查找模板
二分查找有两个模板，区别在于当 r = mid - 1 的时候我们每次求 mid 的时候要 +1，这样可以防止我们的二分查找出现死循环的情况。
模板1
当我们将区间 [l, r] 划分成 [l, mid] 和 [mid + 1, r] 时，其更新操作是 r = mid 或者 l = mid + 1;，计算 mid 时不需要加 1。
int Search_Bin(int l, int r) {
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
模板2
当我们将区间 [l, r] 划分成 [l, mid - 1] 和 [mid, r] 时，其更新操作是 r = mid - 1 或者 l = mid，此时为了防止死循环，计算 mid 时需要加 1。
int Search_Bin(int l, int r) {
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
未完待续，持续更新中……
转载：https://blog.csdn.net/qq_41575507/article/details/108148944