一、搜索插入位置
题目解析
这道题，给定一个数组
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() - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] < target) l = mid + 1;
else if (nums[mid] > target) r = mid - 1;
else return mid;
}
return l;
}
};
二、x 的平方根
题目解析
这道题，给定一个非负整数
x，让我们计算它的算术平方根。注意：我们返回类型是一个整数，结果只保留整数部分，小数部分要舍去（也就是向下取整）
算法思路
对于这道题，暴力解法：
我们从
0开始向后遍历，依次判断i是不是我们要找的x是算术平方根；这里可以从
x开始向后遍历，查找到第一个i的平方小于等于x的位置。
暴力解法遍历的区间是 [1 , x]，我们遍历过程中要判断 i 的平方是否等于 x（或者大于）
但是我们思考一下 [1 , x] 区间内数的平方它是递增的；
当我们遍历一个位置 i 时，那 [1, i-1] 区间内任意一个数的平方都小于 i 的平方；区间 [i+1 , x] 内的任意一个数的平方都是大于 i 的平方的。
所以我们就可以使用二分查找来查找平方 <=x 区间的左端点。
首先定义
left,right(初始值为0和x)，然后取mid = left +(right - left + 1)/2如果mid*mid<x：此时左边区间数的平方都是小于x，肯定不会是最终结果；left = mid。如果mid*mid>x：此时右边区间数的平方都是大于x，mid平方也是大于x的，肯定也不会是最终结果；right = mid - 1。如果mid*mid==x：此时就找到了x的算数平方根，返回结果即可。最后遍历结束
left和right指向位置就是最终结果。
暴力解法遍历的区间是 [1 , x]，我们遍历过程中要判断 i 的平方是否等于 x（或者大于）
代码实现
class Solution {
public:
int mySqrt(int x) {
long long left = 0, right = x;
while (left < right) {
long long mid = left + (right - left + 1) / 2;
long long sum = mid * mid;
if (sum > x) right = mid - 1;
else if (sum < x) left = mid;
else return mid;
}
return left;
}
};
三、山脉数组的峰顶索引
题目解析
对于这道题，给定一个数组
nums，数组中的数据大小是山峰形状的（也就是先递增，然后再递减）现在我们要找到，山峰峰顶的索引值；也就是先递增再下降的转折点。
算法思路
暴力解法：
遍历数组，找到呈下降趋势的起始位置。
简单来说就是遍历数组，如果当前位置是小于下一个位置的值，也就是下降趋势就继续遍历；
如果当前位置是大于下一个位置的值的，也就是上升趋势就返回结果即可。
题目中说，数组中的值是先递增到一个值再递减的，那也就是说我们遍历一个位置 i 时，只存在以下两种情况：
- 递增：
nums[i] > nums[i+1] - 递减：
nums[i] < nums[i+1]
所以我们遍历一个位置
i时：如果当前是递增趋势 (nums[i] < nums[i+1])，那区间[l,i]就是递减的，我们要找的最终结果肯定是在区间[i+1, r]中的；如果当前是递减趋势，也就是nums[i] > nums[i+1]，那区间[i+1, r]就是递减的，而i位置也可能是我们最终要找的结果，所以我们要找的最终结果肯定是在区间[l,i]中的。所以这道题我们就可以使用二分查找来搜索山峰的峰顶位置。
二分查找
这里我们通过上面分析我们可以发现，我们可以将区间分成两部分，一部分是不满足条件的，一部分可能满足条件的；
而这里我们要找的是递减区间的左端点。
首先定义
left,right(初始值为0和n-1)，然后取mid = left +(right - left)/2如果nums[mid] < nums[mid+1]：此时区间[left , mid]是不满足条件的，就要去区间[mid+1 , right]中查找最终结果。如果nums[mid] > nums[mid+1]：此时区间[mid+1 , right]是不满足条件的，就要去区间[left , mid]中查找最终结果。最后遍历结束，
left和right指向的就是最终结果。
代码实现
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int l = 0, r = arr.size() - 1;
while (l < r) {
int mid = (l + r) / 2;
if (arr[mid] > arr[mid + 1]) r = mid;
else l = mid + 1;
}
return l;
}
};
