二分查找算法的介绍
想必大家对这个算法应该不算陌生了，在C语言阶段就已经学习过了。 其是在暴力枚举的基础上进行优化的。例如：在一个有序数组中查找某个元素是否存在。
但是二分查找算法也有缺点，就是需要数据有二段性，不一定是数组全部有序。
二分查找算法其实也是双指针算法中对撞指针的一种拓展，主要是利用了数据的二段性。
下面我们就来进行练习。
704. 二分查找
题目：
给定一个
n个元素有序的（升序）整型数组nums和一个目标值target，写一个函数搜索nums中的target，如果目标值存在返回下标，否则返回-1。
示例 1:输入:nums = [-1,0,3,5,9,12], target = 9输出: 4 解释: 9 出现在 nums 中并且下标为 4示例 2:
输入:nums = [-1,0,3,5,9,12], target = 2输出: -1 解释: 2 不存在 nums 中因此返回 -1提示：
- 你可以假设
nums中的所有元素是不重复的。n将在[1, 10000]之间。nums的每个元素都将在[-9999, 9999]之间。
思路：这里既可以使用最简单的暴力枚举，也可以使用二分查找来解决。
代码实现：
暴力枚举：
class Solution {
public int search(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
return i;
}
}
return -1;
}
}二分查找：
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
while (left <= right) { // 这里得判断=的情况
int mid = (left+right) / 2; // 这里可能会有溢出的风险
if (nums[mid] > target) {
right = mid-1;
} else if (nums[mid] < target) {
left = mid+1;
} else {
return mid;
}
}
return -1;
}
}注意：由于本题数据量不是很大，因此 mid = (left+right) / 2; 就不会溢出，但是当数据量非常大时，两者相加就会导致溢出。有小伙伴可能会有疑惑：left 为 0，right 在 int 中，为什么会导致溢出呢？确实这种情况是正常的，但是当第二次计算mid 且left 为上一次的mid 值呢？这就会溢出了。解决办法为：mid = left + (right - left)/2；上面这个题目只是来练练手，下面才开始真正的算法题。
34. 在排序数组中查找元素的第一个和 最后一个位置
题目：
给你一个按照非递减顺序排列的整数数组
nums，和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值
target，返回[-1, -1]。你必须设计并实现时间复杂度为
O(log n)的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]示例 2：
输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]示例 3：
输入：nums = [], target = 0 输出：[-1,-1]提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109nums是一个非递减数组-109 <= target <= 109
思路：题目说给的数组是非递减的，什么意思呢？
这里要查找的不是一个元素，而是一组连续的数据，也就是一段连续的子区间。 这里可能有小伙伴会想到我们前面学习的滑动窗口算法求子序列的问题。 但是这里不应该优先使用这个方法，因为滑动窗口算法是同向双指针， 而这里我们推测出了数据的特性，应该优先使用二分查找。
这里是要查找一组数据的端点下标，那么我们就可以直接忽略这组数据的中间，直接找端点即可。那么这就从查找一段数据，变为了查找两个值。但是新的问题又来了，怎么找端点呢？相信有聪明的小伙伴已经想到怎么做了。直接暴力枚举去遍历数组就完了。没错，这虽然是一个笨办法，但是总好过没有办法。
遍历的方式：从数组最左端开始遍历，找左端点，接着从数组最右端开始，找右端点即可。
代码实现：
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] ans = {-1,-1};
if (nums.length == 0) { // 排除特殊情况
return ans;
}
// 找左端点
int left = 0;
while (left < nums.length && nums[left] != target) { // 防止越界
left++;
}
if (left == nums.length) { // 数组中没有目标值
return ans;
} else {
ans[0] = left;
}
// 找右端点
int right = nums.length-1;
while (right >= 0 && nums[right] != target) { // 防止越界
right--;
}
if (right >= 0) {
ans[1] = right;
}
return ans;
}
}虽然这是暴力枚举，但是从力扣上面的结果来看，还是不错的。
上面的方法可以说是流氓做法了，不符合题目的要求：用二分查找来解决。
二分查找同样还是去找符合数据的左端点和右端点。
寻找左端点过程：
寻找右端点过程（精简版）：
上面处理这么多，其实就是在证明三件事：
1、根据查找的端点位置，从而划分了合法区域和非法区域，因为端点位置肯定是在有效区域内的。再根据 left 和 right 的相对位置来判断下一步的走向。
左端点：left = mid + 1 ---> 跳出非法区域；right = mid ---> 保留在合法区域。
右端点：left = mid ---> 保留在合法区域；right = mid -1 ---> 跳出非法区域。
2、在查找的过程中，中点的选取。根据查找的端点位置和第一点的结论，从而决定中点的位置。
左端点：right = mid 的特性可能会导致最后死循环，因此中点尽量要靠左，即 mid = left + (right-left) / 2。
右端点：left = mid 的特性可能会导致最后死循环，因此中点尽量要靠右，即 mid = left + (right-left +1) / 2。
3、 查找左端点和右端点的过程中，循环条件只能是 left < right，绝不能出现等于的情况，可能会导致死循环。因为一旦相遇并且结果满足 right 或者 left 不动的情况，那么就会死循环。
上面这些细节问题处理完之后，代码就比较好写了。
代码实现：
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] ans = {-1,-1};
if (nums.length == 0) { // 排除特殊情况
return ans;
}
// 找左端点
int left = 0;
int right = nums.length-1;
while (left < right) {
int mid = left + (right-left) / 2; // 找靠左的位置
if (nums[mid] >= target) {
right = mid; // 保证在合法区域内
} else {
left = mid+1; // 保证有可能跳出非法区域
}
}
// 走到这里，说明left与right相遇了
if (nums[left] == target) { // 判断是否为左端点
ans[0] = left; // left 与 right 都是可以的
} else { // 说明数组中没有要找的数据
return ans;
}
// 找右端点
left = 0;
right = nums.length-1;
while (left < right) {
int mid = left + (right-left+1) / 2; // 找靠右的位置
if (nums[mid] <= target) {
left = mid; // 保证在合法区域内
} else {
right = mid-1; // 保证有可能跳出非法区域
}
}
// 走到这里，说明left与right相遇了
if (nums[right] == target) { // 判断是否为右端点
ans[1] = right; // left 与 right 都是可以的
}
return ans;
}
}还有两个要注意的地方：
因此数组中一旦存在我们要查找的数据的话，肯定是存在左右端点的。
35. 搜索插入位置
题目：
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为
O(log n)的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5 输出: 2示例 2:
输入: nums = [1,3,5,6], target = 2 输出: 1示例 3:
输入: nums = [1,3,5,6], target = 7 输出: 4提示:
1 <= nums.length <= 104-104 <= nums[i] <= 104nums为 无重复元素 的 升序 排列数组-104 <= target <= 104
思路：这里和第一题有点类似，但不同的是这一题的数组中可能不存在 target 这个数据。但是方法还是类似的。
当 [target，right] 区间是合法区间时，right = mid ---> 保证 right 在合法区间内，left = mid+1 ---> 保证 left 有可能进入合法区间，mid = left + (right - left) / 2 ---> 靠左的位置。同理，当[left，target]为合法区间时，也是类似的，这里就不过多赘述了。
代码实现：
1、当 [left, target] 是合法区间时：
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
// 假设[left, target]是合法区间
while (left < right) {
int mid = left + (right-left+1) / 2;
if (nums[mid] > target) {
right = mid-1;
} else {
left = mid;
}
}
// 判断是否存在
if (nums[left] == target) { // 实际存在
return left;
} else { // 不存在
// 判断是插入左边还是右边位置
if (nums[left] > target) {
return left;
} else {
return left+1;
}
}
}
}2、 当 [target，right] 是合法区间时：
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
// 假设[target, right]是合法区间
while (left < right) {
int mid = left + (right-left) / 2;
if (nums[mid] >= target) {
right = mid;
} else {
left = mid+1;
}
}
// 判断是否存在
if (nums[left] == target) { // 实际存在
return left;
} else { // 不存在
// 判断是插入左边还是右边位置
if (nums[left] > target) {
return left;
} else {
return left+1;
}
}
}
}69. x的平方根
题目：
给你一个非负整数
x，计算并返回x的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如
pow(x, 0.5)或者x ** 0.5。
示例 1：
输入：x = 4 输出：2示例 2：
输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。提示：
0 <= x <= 231 - 1
思路： 题目让我们求一个大于等于0整数的算术平方根，并且对最终结果进行向下取整。
方法一：直接暴力枚举即可。
代码实现：
class Solution {
// 暴力枚举
public int mySqrt(int x) {
if (x == 0 || x == 1) { // 排除特殊情况
return x;
}
for (long i = 1; i <= x; i++) {
if (i * i == x) {
return (int)i;
} else if (i * i > x) {
return (int)i-1;
}
}
return -1; // 这里只是过审
}
}注意：由于最后面的 return -1；只是为了让我们的代码编译通过，并不起实际的作用。
我们前面的暴力枚举就是把 [1，x] 之间的数据按照升序的方式挨个使了个遍。 从这里我们就可以使用二分查找算法了。
其实我们最终的目的就是为了找到大于或者的结果，然后再让大于的-1，等于的不变，而这些只能让 target 和 left 在一起。
代码实现：
class Solution {
// 二分查找
public int mySqrt(int x) {
if (x == 0 || x == 1) { // 排除特殊情况
return x;
}
long left = 1;
long right = x;
// 最终的结果是向下取整的，即 <= 是合法区域的
while (left < right) {
long mid = left + (right-left+1) / 2;
if (mid*mid > x) {
right = mid-1;
} else {
left = mid;
}
}
// 找到了
return (int)left;
}
}注意：
1、数据量是比较大的，因此相乘的结果会溢出，我们得用 long类型来接收。
2、这里的二分查找是不能使用第一道题的那种的。
其实没弄明白也没关系，这里反正就两种情况，可以直接去套用，再不济暴力枚举总可以了吧。
总结
1、对于查找固定的数据的情况，可以使用第一题中的二分查找方法：根据要查找的结果，进行比较分为三种情况——大于、等于、小于。
2、对于范围(区间)查找和不确定性查找的情况，可以使用我们后面画图推出来的二分查找：根据查找的结果，进行比较分为两种情况——合法区域、非法区域（根据要查找的数据进行分区），然后再分别更新 left 和 right——合法的一定要确保依旧存在于合法区域，非法的要确保有希望调到合法区域。再就是计算中点的方式和循环条件的确定，都是由 left 和 right 的变化来决定的（具体可见图）。
我们以后常用的也是第二种二分查找的方法。
好啦！本期 二分查找算法专题（1）的学习之旅就到此结束啦！我们下一期再一起学习吧！
