二分查找算法实战：插入位置、平方根与峰顶索引

一、搜索插入位置

题目解析

这道题，给定一个数组 nums 和一个目标值 target，让我们在数组 nums 中找到目标值；如果目标值存在就返回它的下标，如果不存在就返回数 target 被顺序插入的位置下标。

算法思路

这道题，我们可以使用暴力查找，时间复杂度是 O(n)。

从左到右遍历数组，找到值大于等于 target 的起始位置（如果 target 不存在，那要找的就是 target 顺序插入的位置）

题目要求我们要使用时间复杂度为 O(log n) 的算法来解决，暴力解法的时间复杂度为 O(n)（暴力解法虽然可以通过这道题）

思考以下：数组 nums 是有序的，且我们要找的是 >=target 的起始位置，那也就是大于等于 target 区间的左端点；

我们再随机挑选一个位置 i，区间 [0,i-1] 中的数都是小于 i 位置的数；区间 [i+1 , n] 中的数都是大于 i 位置的数的。

那我们就可以使用二分查找

首先定义 left 和 right 指向数组的起始位置和结束位置。取 mid = left + (right - left)/2 比较 mid 位置的值和 target 如果 nums[mid] > target，就去左边区间查找；right = mid - 1。如果 nums[mid] < target，就去右边区间查找；left = mid + 1。如果 nums[mid] == target，就查找到了 target，就返回当前位置下标即可。这里因为我们要查找的是 >=target 区间的左端点，所以在遍历结束后，l 指向的就是 target 顺序排序的插入位置。

代码实现

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - ;
         (l <= r) {
             mid = (l + r) / ;
             (nums[mid] < target) l = mid + ;
              (nums[mid] > target) r = mid - ;
              mid;
        }
         l;
    }
};