二分查找练习总结以及解题模板总结
最近在刷二分查找相关的题，由于二分查找不只限于这一道简单的题，而是一类题的解题思路，因此在这里简单做一个总结。
一、二分查找的母题
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
这是leetcode上的第704题，感兴趣的同学可以去看看具体的题目要求。
二分查找的时间复杂度为o(log n)，查找效率要比遍历高不少，但是用二分查找有两个前提，①有序数组②数组中无重复元素。并不是使用二分这个思想做题就一定得遵循这两条，在后面的题目中有所体现，请耐心看完。
二分查找主要是通过衡量nums[mid]与目标值之间的大小关系，以此判断究竟是将查找区间前移（right = mid - 1）还是后移（left = mid + 1）
这里我给出我的题解：
class Solution {
public int search(int[] nums, int target) {
if(target < nums[0] || target > nums[nums.length - 1]){
return -1;
}
int left = 0;
int right = nums.length - 1;
while (left <= right){
int mid = left + ((right - left) >> 1);
if(nums[mid] == target){
return mid;
}else if(nums[mid] < target){
left = mid + 1;
}else{
right = mid - 1;
}
}
return -1;
}
}
二、二分查找思想的使用
这里着重强调一点，当题目中出现 为无重复元素的升序排列数组或时间复杂度为o(log n)这样的词时，就应该着重考虑二分查找
1.leetcode 35题
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
这道题如果不加上如果目标值不存在于数组中这句话，那就是二分查找本题了，因此根据题设很自然的联想到使用二分查找。这里需要注意一下，二分查找的本体永远是while循环，且while循环的终止条件永远都是left > right，且最后越界时left都比right大1，然后根据具体题目的要求，看需要返回啥东西，确定while循环结束后return什么即可
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = left + ((right - left) >> 1);
if(nums[mid] > target){
right = mid - 1;
}else if(nums[mid] < target){
left = mid + 1;
}else{
return mid;
}
}
return left;
}
}
2.leetcode 34题
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
关键字和O(log n) 再次表明，这道题需要使用二分查找，但实际上这道题我也是理解了别人的题解，然后自己一步一步推出来的（惭愧，刚开始刷题，还是太菜）
以我对这道题的理解所能提供的建议，求左边界和右边界的函数只需从思想上入手，即二分查找的本质，不然从具体推抽象真的不好想
这道题和真正的二分有一个区别，那就是数组可能存在重复元素，且要求这个元素的起始和终止位置，因此就不能在nums[mid] == target时进行return操作，分别在求左边界和右边界时和nums[mid] > target 、nums[mid] < target合并。以求左边界为例，在跳出while循环时，left和right所处的位置，left一定是在区间的第一个位置上，right一定在区间的前一个位置上（可以自己举个例子试一下），这也是二分的本质，在跳出二分的while循环时，left一定是在right右边的第一个位置上，这一点多举例子后就能深刻理解。
代码如下：
class Solution {
public int[] searchRange(int[] nums, int target) {
int leftborder = leftBorder(nums,target);
int rightborder = rightBorder(nums,target);
if(leftborder == -2 || rightborder == -2){
return new int[]{-1,-1};
}
if(rightborder - leftborder > 1){
return new int[]{leftborder + 1, rightborder - 1};
}
return new int[]{-1,-1};
}
public int getLeftBorder(int[] nums,int target){
int left = 0;
int right = nums.length - 1;
int leftborder = -2;
while(left <= right){
int mid = left + ((right - left) >> 1);
if(nums[mid] < target){
left = mid + 1;
}else{
right = mid - 1;
leftborder = right;
}
}
return leftborder;
}
public int getRightBorder(int[] nums,int target){
int left = 0;
int right = nums.length - 1;
int rightborder = -2;
while(left <= right){
int mid = left + ((right - left) >> 1);
if(nums[mid] > target){
right = mid - 1;
}else{
left = mid + 1;
rightborder = left;
}
}
return rightborder;
}
}
3.leetcode 69题
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
代码如下：
class Solution {
public int mySqrt(int x) {
if(x == 1 || x == 0){
return x;
}
int left = 0;
int right = x;
while(left <= right){
int mid = left + ((right - left) >> 1);
if(mid > x/mid){
right = mid -1;
}else if(mid < x/mid){
left = mid + 1;
}else{
return mid;
}
}
return right;
}
}
4 leetcode 367题
给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要 使用任何内置的库函数，如 sqrt 。
这道题和上道题一样，属于二分查找while循环里if条件随实际题意改变而改变的题，就是判断条件
class Solution {
public boolean isPerfectSquare(int num) {
int left = 1;
int right = num;
while(left <= right){
int mid = left + ((right - left) >> 1);
long sqrt = (long)mid * mid;
if(sqrt > num){
right = mid - 1;
}else if(sqrt < num){
left = mid + 1;
}else{
return true;
}
}
return false;
}
}
总结
当题目中出现有序数组、时间复杂度O(log n)、无重复元素等字眼时，首先考虑二分查找，其次也不是必须无重复元素才能用二分查找，在寻找区间左边界和右边界时可也使用二分查找（34题主要利用了当跳出while循环时，left是比right大1这一条特性的），因此需要灵活使用。此外二分查找的while循环里if的判断条件也不是固定的，随题意的变化而变化，因此要具体问题具体分析（以69题和367题为例）。
|