算法细节系列（5）：二分查找应用
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434844
二分查找应用
题目来源于leetcode：https://leetcode.com/tag/binary-search/
ID | Title | Acceptance | Difficulty |
|---|---|---|---|
35 | Search Insert Position | 39.3% | Easy |
367 | Valid Perfect Square | 37.8% | Easy |
153 | Find Minimum in Rotated Sorted Array | 39.2% | Medium |
154 | Find Minimum in Rotated Sorted Array II | 36.6% | Hard |
35.Search Insert Position
详见连接：https://leetcode.com/problems/search-insert-position/#/description
public int searchInsert(int[] nums, int target) {
int lf = 0, rt = nums.length-1;
while (lf < rt){
int mid = lf + (rt - lf) / 2;
if (nums[mid] < target){
lf = mid + 1;
}else{
rt = mid;
}
}
//边界条件
if (nums[rt] < target) return rt + 1;
return rt;
}考点为lf和rt的变动，以上是闭区间的解决方案。主要注意边界条件的使用，需要对数组最后一个元素进行边界判断。
367. Valid Perfect Square
详见链接：https://leetcode.com/problems/valid-perfect-square/#/description
public class Solution {
public boolean isPerfectSquare(int num) {
if (num == 0) return false;
int end = binarySearch(num, num);
return end == -1 ? false : true;
}
private int binarySearch(int num, int target){
int lf = 1, rt = num; //闭区间
while (lf < rt){
int mid = lf + (rt - lf) / 2; //防止溢出
if (target / mid > mid){
lf = mid + 1;
}else{
rt = mid;
}
}
if (target % rt == 0 && target / rt == rt) return rt;
return -1;
}
}官网还有其它两种解法，此处主要用二分查找。简单叙述下它的思想，假设nums = 9，那么我们可以构造一个”数组”，或者称为解空间更合适。
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|
1 | 4 | 9 | 16 | 25 | 36 | 49 | 64 | 81 |
那么我们只需要在给定的解空间内找寻到对应的nums，很明显我们能在1~9的解空间内，找到对应的9，需要注意一点！为了防止大数相乘溢出，这里判断语句为target / mid > mid，把这部分解给排除后，循环外还需要增加一个额外的判断，如 42 / 6 > 6，但是它并不是Perfect Square.
153. Find Minimum in Rotated Sorted Array
详见链接：https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/#/description
public int findMin(int[] nums) {
if (nums.length == 1) return nums[0];
int lf = 1, rt = nums.length -1;
while (lf < rt){
int mid = lf + (rt - lf) / 2;
if (nums[mid] > nums[mid-1] && nums[mid] > nums[rt]){
lf = mid + 1;
}else{
rt = mid;
}
}
//边界条件
if (nums[rt] > nums[rt-1]) return nums[rt-1];
return nums[rt];
}这是一种解法，需要注意nums[mid] > nums[mid-1]，所以lf的初始值必须在1，否则会越界。单纯的这个条件是无法找到最小的，原因如下，当数组没有发生旋转时，它的切分不断向rt靠近，显然离想要搜索的越来越远，所以还需要加上nums[mid] > nums[rt]如果存在旋转，且搜索的最小值在右侧，必然割掉左半部分。边界条件的考虑在于，如果没有旋转的数组，while循环一直走rt = mid，那么必然rt会慢慢接近lf = 1，针对这个问题我们要额外的边界条件去判断。
其实有一种方式可以帮助我们理解，我们要找的是最小，但二分的目的在于丢弃一部分而去搜索另一部分，所以终极目标在于找到左半部分和右半部分的唯一区别的条件，如果能把它们唯一区分，那就自然能解。
这里有一种更优美的方式，我们只需要加一个条件即可。nums[mid] > nums[rt]，这就能区分左和右了。所以有
public class Solution {
public int findMin(int[] nums) {
int lf = 0, rt = nums.length -1;
while (lf < rt){
int mid = lf + (rt - lf) / 2;
if(nums[mid] > nums[rt]){
lf = mid + 1;
}
else{
rt = mid;
}
}
return nums[rt];
}
}好处很明显，nums[mid] < nums[rt]时，rt会不断向lf靠近，而因为没有了mid-1所以lf可以取0，那么自然而然的边界就不需要再考虑了。而左半部分也能被清楚的区分，一举两得。
154. Find Minimum in Rotated Sorted Array II
详细链接：https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/#/description
public class Solution {
public int findMin(int[] nums) {
int lf = 0, rt = nums.length -1;
while (lf < rt){
int mid = lf + (rt - lf) / 2;
if (nums[mid] > nums[rt]){
lf = mid + 1;
}else if(nums[mid] < nums[rt]){
rt = mid;
}else{
rt --;
}
}
return nums[rt];
}
}好吧，我是看了解决方案才理解的，没有想到当相等情况下，直接对rt--就好了，它主要针对如下情况：
3,3,3,3,3,3,3,3,3,3,3,1,3,3
if和else前面已经说了很多了，我不多说，主要遇到nums[mid] == nums[rt]时，rt--的确很巧妙！！！如果把这个等号放在if中，那么会出现1,2,3,3,3,3,3,3,3检测出错的情况，原因在于lf会不断向rt靠近，但显然在它的搜寻路径中是找不到最小值的，为了规避这种情况，我们让相等时rt--，那么不管上面哪两种情况，它都能解决了，呵呵，想不到。
腾讯云开发者
