我学二分查找遇到的坑与解决的办法

前言

本文聚焦最简单的二分查找，集中讨论那些我们不曾注意的问题，解开二分查找不简单的一面，在本文中笔者将带你重新认识二分查找

引子

有数量为n的硬币，和一个天平，已知其中有一个假币，且假币比真币轻，请找出这枚假币

我记得这种题目是在我小学遇到过的，那时候虽然不知道什么二分查找法，但脑袋一偏自然也能想到：把硬币两半分，假币就在轻的一堆，然后不断的分成均匀的两堆，最后总能找出假币，这么看来二分查找似乎是一种很常识的东西，对！它确实简单，如果要一个人手写快排，他可能不一定能写得出来，但要他写二分查找，那他肯定行！下面是常见的一种二分查找的 demo：

  
public int search(int[] arr, int target){
        int left = 0, right = arr.length-1;
        while (left <= right){
            int mid = left+(right-left>>1);
            if (target == arr[mid]){
                return mid;
            }else if (arr[mid] < target){
                left = mid+1;
            }else if (arr[mid] > target){
                right = mid-1;
            }
        }
        return -1;
    }

我就经常这样写，不过每次我都有几个地方拿不准：

right = arr.length - 1 or right = arr.length
while (left < right) or while (left <= right)
mid = (left + right) / 2，mid = (left + right) >> 1 or mid = left + (right - left) / 2，这三种写法有什么区别？
mid = left + (right - left ) / 2 or mid = left + (right - left + 1) / 2
left = mid + 1 or left = mid，right = mid - 1 or right = mid

😮欸？被我这么一提，你是不是也发现事情好像根本没那么简单？！😮

😁没事，下面跟着笔者一起来探讨，看看这二分查找到底是个什么妖怪？😁

概念须知

搜索区间

可以说做二分查找这类的题目一定要有区间的概念，所谓的搜素区间就是我们指定的查找范围，也就是 left 和 right 之间的这段。而且随着我们不停的二分，搜索区间将会被不断分割并缩小直到找出目标数据或者搜索区间为空。这里先提一下：一定要让你的搜索区间能够正常缩小，否则会产生严重的问题！

判空条件

也就是 while 里面的条件判断，当搜索区间为空时循环跳出，对于不同的判空条件有以下三种情况：

while(left <= right) left == right+1，跳出循环，此种情况下左右边界值也会被取到，搜索区间相当于 [left，right]
while(left < right) left == right，循环跳出，搜索区间相当于 [left，right)
while(left < right-1) left == right-1，循环跳出，搜索区间相当于 [left，right-1)，这个情况其实是我总结出来的一种技巧，对解决一种问题非常有用，在这容许笔者先卖个关子，后续会为你揭晓

从这几种情况来看，判空条件决定了每次你进行搜索的有效区间，请看下面：

判空条件	搜索区间
while(left <= right)	[left，right]
while(left < right)	[left，right)
while(left < right-1)	[left，right-1)

向下取整、向零取整

整数除法 /	右移运算 »
向零取整	向下取整

例如：(-4-5) ÷ 2 = -4.5，向零取整等于-4，向下取整等于-5

验证：

  
System.out.printf("整数除法%d，右移运算%d",(-4-5)/2, (-4-5)>>1);

测试结果：

整数除法-4，右移运算-5

如何正确的搭配

回到我们文章开头最初的写法，请稍稍思考下面的问题：

一定要这么写吗？
我可以随意组合吗？
随意组合后可能会出现什么问题？

  
public int search(int[] arr, int target){
        int left = 0, right = arr.length-1;
        while (left <= right){
            int mid = left+(right-left>>1);
            if (target == arr[mid]){
                return mid;
            }else if (target > arr[mid]){
                left = mid+1;
            }else if (target < arr[mid]){
                right = mid-1;
            }
        }
        return -1;
    }

这段程序是为了在一个给出的搜索区间中找出目标数据，下面我们从头至尾分析：

1.为什么是 left <= right 前面已经说了，判空条件决定了你的搜索区间，也就是此时我们的搜索区间是 [0，arr.length-1]，假设你要选择左闭右开的搜索区间，也就是[0，arr.length-1)，那么当搜索区间缩小至 [arr.length-1，arr.length-1) 时，循环跳出，但有效数据 arr[arr.length-1] 还没来得及与 target 进行比较，显然这样的程序存在隐患，它并不完美。所以你可以选择修改判空条件为 left <= right，但你也可以选择加个补丁，就像下面这样：

  
public class BinarySearch {
    public int search(int[] arr, int target){
        int left = 0, right = arr.length-1;
        while (left < right){
            int mid = left+(right-left>>1);
            if (target == arr[mid]){
                return mid;
            }else if (target > arr[mid]){
                left = mid+1;
            }else if (target < arr[mid]){
                right = mid-1;
            }
        }
// 补丁：防止忽略本该比较的数据
        if (arr[left] == target)
            return left;
        return -1;
    }
}
public class BinarySearchTest {
    public static void main(String[] args) {
        int[] nums = {9, 13, 17, 19, 25};
        int[] target = {7, 9, 10, 13, 17, 19, 22, 25, 28};
        BinarySearch binarySearch = new BinarySearch();
        for (int i=0; i<target.length; ++i){
            System.out.println("index：" + binarySearch.search(nums, target[i]));
        }
    }
}

测试结果

  
index：-1
index：0
index：-1
index：1
index：2
index：3
index：-1
index：4
index：-1

2.为什么是 mid = left+(right-left»1) ，mid = left+(right-left+1»1) 可以吗？

>> 与 / 只在数值为负值时会有区别，正数并没有区别
left+(right-left) 能在一定程度上避免因 (left+right) 过大而导致的数值溢出
当 right-left = 1 时，left+(right-left » 1) = left，left+(right-left+1 » 1) = right，下面笔者将给出一个示例告诉你后者的危险在哪？

  
public class BinarySearch {
    public int search(int[] arr, int target){
        int left = 0, right = arr.length-1;
        while (left < right){
            int mid = left+(right-left+1>>1);
            if (target == arr[mid]){
                return mid;
            }else if (target > arr[mid]){
                left = mid+1;
            }else if (target < arr[mid]){
                right = mid-1;
            }
        }
        // 补丁：防止忽略本该比较的数据
        if (arr[left] == target)
            return left;
        return -1;
    }
}
public class BinarySearchTest {
    public static void main(String[] args) {
        int[] nums = {19, 25};
        int[] target = {28};
        BinarySearch binarySearch = new BinarySearch();
        for (int i=0; i<target.length; ++i){
            System.out.println("index：" + binarySearch.search(nums, target[i]));
        }
    }
}

测试结果：

  
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 2 out of bounds for length 2
	at cn.edu.huas.st.flameking.binarysearch.BinarySearch.search(BinarySearch.java:19)
	at cn.edu.huas.st.flameking.binarysearch.BinarySearchTest.main(BinarySearchTest.java:15)

显然发生了数组越界，让我们来看看哪个地方出错了：

数组越界可见在第一轮循环中，left = mid+1 = 2，已经超出了数组的有效访问范围。那么该如何解决呢？
第一：如源程序所示：left = mid+1，right = mid-1，因此区间的分割和缩小并没有问题
第二：判空条件产生的有效数据忽略比较的问题也因为打上了补丁得到了解决
那么我们再对数组越界产生的问题打个补丁不就行了，如下：

  
public class BinarySearch {
    public int search(int[] arr, int target){
        int left = 0, right = arr.length-1;
        while (left < right){
            int mid = left+(right-left+1>>1);
            if (target == arr[mid]){
                return mid;
            }else if (target > arr[mid]){
                left = mid+1;
            }else if (target < arr[mid]){
                right = mid-1;
            }
        }
// 补丁：对数组越界做出反应        
        if (left >= arr.length)
            return -1;
// 补丁：防止忽略本该比较的数据        
        if (arr[left] == target)
            return left;
        return -1;
    }
}

读者可以利用上面给出的测试数据进行测试，当然也可以自己设计测试数据进行验证。

3.为什么是 left = mid+1，right = mid-1

在判空条件的约束下我们的实际搜索区间是[left，right]，对于不合格的mid应当抛弃，如果left = mid 或者 right = mid 抑或是左右边界均没有正常取舍，就会导致区间不正常分割而达不到缩小的目的，这样会陷入一种很严重的错误：死循环。那么该如何解决呢？很简单，让区间能够正常缩小就行了。下面对三种情况依次进行解决：

  
public class BinarySearch {
    /**
     * left = mid
     * @param arr
     * @param target
     * @return
     */
    public int search(int[] arr, int target){
        int left = 0, right = arr.length-1;
// 3. 避免左右边界相等但没有找出目标，并由于左边界不正常分割导致死循环，所以要在 left=right 的时候及时跳出循环
        while (left < right){
// 2. 因为此时右边界正常缩小所以 让 mid = (left+right+1)/2 = right
            int mid = left+(right-left+1>>1);
            if (target == arr[mid]){
                return mid;
            }else if (target > arr[mid]){
/** 1. 左边界分割错误 也就是说如果发生： left = （mid = （left+right）/2） 就会陷入死循环,
那么我们让它不等于就 Ok 了,同时让它在边界相等时跳出循环 */
                left = mid;
            }else if (target < arr[mid]){
                right = mid-1;
            }
        }
// 4. 对没来的及进行比较的数据，进行补充比较
        return arr[left] == target ? left : -1;
    }
}

  
public class BinarySearch {
    /**
     * right = mid
     * @param arr
     * @param target
     * @return
     */
    public int search(int[] arr, int target){
// 4. 如果你不想打上麻烦的补丁，right = arr.length 这样在 [left，right) 的搜索区间下就不会忽略掉有效数据了
        int left = 0, right = arr.length;
// 2. 避免 left = right 没有退出循环的情况
        while (left < right){
            int mid = left+(right-left>>1);
            if (target == arr[mid]){
                return mid;
            }else if (target > arr[mid]){
                left = mid+1;
            }else if (target < arr[mid]){
/** 1. 右边界分割错误 由于左边界分割正常，同时 当 right-left=1 时 （left+right）/2 = left，所以可能出现的错误情况应当是 left = right
但还没有找出目标数据而陷入死循环   */
                right = mid;
            }
        }
// 3. 补丁：比较在循环中被忽略的数据
//        return arr[left] == target ? left : -1;
        return -1;
    }
}

  
public class BinarySearch {
    /**
     * left = mid
     * right = mid
     * @param arr
     * @param target
     * @return
     */
    public int search(int[] arr, int target){
        int left = 0, right = arr.length-1;
// 2. 在 right-left = 1 这个危险的时候尽快跳出循环
        while (left < right-1){
            int mid = left+(right-left>>1);
            if (target == arr[mid]){
                return mid;
            }else if (target > arr[mid]){
                left = mid;
            }else if (target < arr[mid]){
                right = mid;
            }
        }
/** 1. 经过前面的分析，我们发现死循环发生的时机都是在 right-left=1 or left = right 时发生
所以我们及时在两种情况发生之前退出，从根本上消除死循环（😊这就是前面提到的技巧哦😜） */
        if (arr[left] == target)
            return left;
        else if(arr[right] == target)
            return right;
        else
            return -1;
    }
}

好了三种情况笔者都已经分析好，并且给出了参考程序，当然解法有很多种就看你怎么组合，只要解决我列出的下列情况就 Ok 了

常见错误清单

常见错误	出现的时机
有效数据被忽略比较	right = length-1， while(left < right)
数组越界访问	right = length，while(left <= right) `or` right = length-1，mid = left + (right-left+1 » 1)，left = mid+1
死循环	right - left = 1，left=mid，right=mid

基本上只要你规避了以上问题，并且保持区间正常缩小，程序应该就足够 nice 了，==不过也许还有笔者没有遇到的问题，读者可以在下方评论提醒笔者，笔者将会对新问题提出解决方案，并更新本篇文章==。至于上面的问题该怎么解决，程序中我已经写出了详细的分析过程，并给出了测试数据，如果读者不相信我的测试数据也可以自行设计测试数据。看到这想必你对这节开头提出的问题已经有答案了吧！

一定要这么写吗？当然不是
我可以随意组合吗？是的，我们可以随意组合，只要解决我上面总结的错误即可
随意组合后可能会出现什么问题？请看上面的表格【常见错误清单】

应用场景

那么上面的分析就是全部了，既然考前复习做好了，那么就该上考场了，请运用你刚刚学到的知识解决下面的问题，笔者将会给出参考程序

寻找左右侧边界

原题链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

题目：

在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 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] <= 109
nums 是一个非递减数组
-109 <= target <= 109

参考程序

  
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] border = {-1, -1};
// 避免数组为空时，越界访问了
        if (nums.length == 0)
            return border;
// 3. right = nums.lenght 避免打补丁（对忽略数据进行比较）
        int left = 0, right = nums.length;
// 寻找左边界

// 2. 在 left = right 时及时跳出循环
        while (left < right){
            int mid = left + (right-left>>1);
            if(target == nums[mid]){
/** 1. 由于我们寻找的是左边界，所以并不能立即返回，应当保持当前的值，并让区间向左缩小，
 但在 right = left，nums[right] =  target 时定会出现死循环 */
                right = mid;
            }else if(target > nums[mid]){
                left = mid+1;
            }else if(target < nums[mid]){
                right = mid-1;
            }
        }
        if(left !=  nums.length)
          border[0] = nums[left] == target ? left : -1;
// 寻找右边界
        /** 注意别忘记重新初始化 */
        left = 0;
        right = nums.length-1;
// 2. 避免 right - left = 1 的情况 因为这样容易死循环
        while (left < right-1){
            int mid = left + (right-left>>1);
            if(target == nums[mid]){
/** 1. 由于我们寻找的是右边界，所以并不能立即返回，应当保持当前的值，并让区间向右缩小，
 但在 right = left+1，nums[left] = target 或者 right = left，nums[left] = target 时定会出现死循环 */
                left = mid;
            }else if(target > nums[mid]){
                left = mid+1;
            }else if(target < nums[mid]){
                right = mid-1;
            }
        }
        if(nums[right] == target)
            border[1] = right;
        else if(nums[left] == target)
            border[1] = left;

        return border;
    }
}

在单调递增序列a中，查找 >= x 的数中最小的一个（即x或x的后继）

  
public class BinarySearch {
    public int search(int[] a, int x){
        if (a.length == 0)
            return -1;
        int left = 0, right = a.length-1;
// 2. 为了避免 left == right 我们应当在这时跳出循环 所以应当是 left < right
        while (left < right){
            int mid = left+(right-left>>1);
            if (x == a[mid]){
/** 1. 由于我们要找 >= x 的最小一个，也许这个并不是最小的，所以我们并不能立即返回，而应当向左缩小区间
但这样当 left = right 时程序会进入死循环*/
                right = mid;
            }else if (x > a[mid]){
                left = mid+1;
            }else if (x < a[mid]){
                right = mid;
            }
        }
        if (a[left] >= x)
            return a[left];
        return -1;
    }
}
public class BinarySearchTest {
    public static void main(String[] args) {
        int[] nums = {1, 3, 4, 6, 8, 10};
        int[] target = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
        BinarySearch binarySearch = new BinarySearch();
        for (int i=0; i<target.length; ++i){
            System.out.printf("%d的后继是：%d\n", target[i], binarySearch.search(nums, target[i]));
        }
    }
}

测试结果：

  
0的后继是：1
1的后继是：1
2的后继是：3
3的后继是：3
4的后继是：4
5的后继是：6
6的后继是：6
7的后继是：8
8的后继是：8
9的后继是：10
10的后继是：10
11的后继是：-1

在单调递增序列a中，查找 <= x 的数中最大的一个（即x或x的前驱）

  
public class BinarySearch {
    public int search(int[] a, int x){
        if (a.length == 0)
            return -1;
        int left = 0, right = a.length-1;
// 3. 为了避免 left == right 我们应当在这时跳出循环 所以应当是 left < right
        while (left < right){
// 2. 解决 left = right-1 的死循环问题，那么我们就让 mid != left，等于 right 就行了
            int mid = left+(right-left+1>>1);
            if (x == a[mid]){
/** 1. 由于我们要找 <= x 的最大一个，也许这个并不是最大的，所以我们并不能立即返回，而应当向右缩小区间
但这样当 left = right or left = right-1 时程序会进入死循环*/
                left = mid;
            }else if (x > a[mid]){
                left = mid;
            }else if (x < a[mid]){
                right = mid-1;
            }
        }
        if (a[left] <= x)
            return a[left];
        return -1;
    }
}

public class BinarySearchTest {
    public static void main(String[] args) {
        int[] nums = {1, 4, 6, 8, 10};
        int[] target = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
        BinarySearch binarySearch = new BinarySearch();
        for (int i=0; i<target.length; ++i){
            System.out.printf("%d的前驱是：%d\n", target[i], binarySearch.search(nums, target[i]));
        }
    }
}

测试结果：

  
0的前驱是：-1
1的前驱是：1
2的前驱是：1
3的前驱是：1
4的前驱是：4
5的前驱是：4
6的前驱是：6
7的前驱是：6
8的前驱是：8
9的前驱是：8
10的前驱是：10
11的前驱是：10

再次提一下之前提过的小技巧，因为真的很有用，如果害怕处理死循环的问题，那么可以在 right-left = 1 时跳出循环，达到消除死循环的目的，因为经总结死循环往往在 right-left = 1 或 right = left 也就是搜索区间只剩两个数亦或者是只剩一个数的时候出现，跳出循环之后你就可以对左右边界单独进行分析。

尾声

通常只要掌握其中一种标准匹配就已经 OK 了,比如文章开头给出的 demo，但如果想要深入了解二分查找，想要轻松解决二分查找的变式问题，那么就应该对不同写法，不同组合的二分查找有详细的了解，甚至是自己能够随意组合，就像一个魔方无论它怎么打乱，最后都能还原

我学二分查找遇到的坑与解决的办法

前言

引子

概念须知

搜索区间

判空条件

向下取整、向零取整

如何正确的搭配

应用场景

寻找左右侧边界

在单调递增序列a中，查找 >= x 的数中最小的一个（即x或x的后继）

在单调递增序列a中，查找 <= x 的数中最大的一个（即x或x的前驱）

尾声

相关文章

详解桶排序及排序大总结

HashMap遍历的三种方式

优先队列PriorityQueue