二分查找
入坑LeetCode的第一天，跟着代码随想录的路线刷了二分查找的几道题(基于Java)，这里简单分享下题与题解。
二分查找是一种比较基础的算法，思路就是不断取有序数组中间位置的数，与目标数进行比较，如果比目标数大，则说明目标数在当前位置左边(数组升序)，此时更新右边界为当前位置，继续查找中间位置的数。我们在代码实现时重点关注左右区间的设置就可以。下面直接上题。
题1：leetcode_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] 之间。
解题思路：
初学者一开始肯定想到的是从头到尾遍历一遍，但是如果数组很长，会耗费不少时间，专业一点来说就是算法复杂度大了。由题目可知数组升序且不重复，这很符合二分查找的条件。话不多说，开敲：
public static void main(String[] args) {
int[] nums = new int[]{-1, 0, 3, 6, 7, 8, 10, 11, 12, 14, 15};
int target = 15;
int result = binarySearch(nums, target);
if (result != -1){
System.out.println(String.format("成功找到，下标为%d", result));
}
else {
System.out.println(String.format("%d不存在nums中", target));
}
}
// 这里才是用于leetcode提交的部分，main里用来idea自己跑
private static int binarySearch(int[] nums, int target) {
// 二分基本操作，初始化左右下标以及中间位置的下标，当然M也可以至今写在循环中
int L = 0, M = nums.length / 2, R = nums.length;
while (L < R){ // 至于这里是 L<R 还是 L<=R 看个人习惯以及具体题目，注意右边界R的变化就行
if (nums[M] > target)
R = M;
else if (nums[M] < target)
L = M + 1;
else
return M;
M = (L + R) / 2;
}
return -1;
}
类似题：leetcode_35 搜索插入位置，也可以采用二分来做，对于返回值需要做处理变化。
题2：leetcode_69
给你一个非负整数 x ，计算并返回 x 的算术平方根 。由于返回类型是整数，结果只保留整数部分 ，小数部分将被舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5
示例1：
输入：x = 4
输出：2
示例2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去
提示：
- $0 <= x <= 2^{31} - 1$
解题思路：
这道题并没有直接告诉你有什么有序数组，但我们是不是可以认为有 0-x 这样一个整型数组，从中找一个数使得它的平方等于或刚好小于x呢，这样想就又可以用二分来解决。对于while循环中的if判断条件，改成当前数的平方与x相比就可以，即：$M * M < x?$上代码：
private static int mySqrt(int x) {
int L = 0, R = x; //还是一样初始化左右边界
int ans = -1;
while(L <= R){ //注意，这里必须用<=的方法，即右边界必须等于x，因为这里不是用作下标，而是具体参与计算的数，R改变后仍有参与计算的可能
int M = (L + R) / 2;
if ((long) M * M > x) // 当数字过大时，它的平方可能超过int范围，因此需要转换为 long
R = M - 1;
else{
ans = M;
L = M + 1;
}
}
return ans;
}
类似题：leetcode_367 有效的完全平方，解题思路一样，多了一个对是否为完全平方的判断。
题3：leetcode_34 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。
示例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<=10^5$
- $-109<=nums[i]<=109$
- $nums$是一个非递减数组
- $-109<=target<=109$
解题思路：
数组还是非递减，即我们需要找到第一个等于target的下标和最后一个等于target的下标，做了两遍二分，我想大家也不会再继续暴力搜索了吧。那如何用二分来解决呢？可以写两个函数先找左边界，再找右边界，对于这个，代码随想录在leetcode中也做了详细的题解(点此查看)，然后官方也给出了两者合二为一的方法，具体见此题的官方题解。下面上代码(没错，搬运的官方)：
// idea测试
public static void main(String[] args) {
int[] nums = new int[]{2,2};
int target = 2;
int[] result = searchRange(nums, target);
System.out.println(String.format("[%d,%d]",result[0],result[1]));
}
private static int[] searchRange(int[] nums, int target) {
int [] result;
int leftIdx = binarySearch(nums, target, true);
//取得的右边界需要 -1，因为取得是第一个大于而非最后一个等于
int rightIdx = binarySearch(nums, target, false) - 1;
// 对取得的左右边界进行判断
if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target)
result = new int[]{leftIdx,rightIdx};
else
result = new int[]{-1, -1};
return result;
}
// 二分获取下标，boolean用来区分是左边界还是右边界
private static int binarySearch(int[] nums, int target, boolean b) {
int L = 0, R = nums.length;
int res = nums.length;
while (L < R){
int M = L + ((R - L) >> 2);
//第一个条件是寻找第一个大于target的数值下标，即右边界；第二个是寻找第一个等于target的数值下标，即左边界，由于可能不存在与target的相等的数值，故可以用'>='合二为一
if (nums[M] > target || (b && nums[M] >= target)){
R = M;
res = M;
}
else {
L = M + 1;
}
}
return res;
}
总结：
以上就是入坑leetcode第一天刷的题，也开始学着总结，在一位up主(天天向上的锐)的视频推荐下选择了代码随想录(微信公众号同名)作为javaSe以及算法学习巩固的路线参考。另外，对于刷过的题也需要复习巩固，初学者可以跟着敲然后理解成自己的思路，最后能够自己盲敲。
以上就是小编对于二分查找的学习分享，愿能保持总结，也愿大家保持学习状态。