我爱学算法之—— 二分查找（中）

一、搜索插入位置

题目解析

在这里插入图片描述

这道题，给定一个数组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;elsereturn 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;elsereturn 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;elsel = mid+1;}return l;}
};