二分查找专题 - 基础篇

电玩女神 2021-09-10 07:48 277阅读 0赞

## 二分查找 - 基础篇 ##

## 前言 ##

从一个有序的数组中，找到某元素的值，通常思路就是二分查找。二分查找是一个常考的知识点。同时，它也是非常容易出错的一道面试题。左右指针的位置，取值，比较是大于还是大于等于。里面细节很多。死记硬背往往容易出错，只有真正理解思路和多多练习，才能掌握不出错的”二分算法“。

本篇文章是二分查找的入门篇。将会介绍最传统，最容易理解与书写的二分算法。并介绍四种二分查找的进阶问题。在理解本文的基础上，后续文章将会再分享二分的各种变形和其他模板。

## 原题：在有序数组中查找定值 ##

思路很简单，利用数组有序的特性，每次将数组二分，拿中间元素和目标值比较。中间元素和目标值相等，直接返回下标索引。中间元素比目标值小，则去右区间继续二分查找，否则去左区间二分查找。

代码如下，并不复杂，但有几个需要注意的细节：

1.  **循环条件**
    
    比较大小使用 <= 小于等于号
2.  **防止死循环**
    
    更新low，high指针分别取值mid + 1 和 mid -1，注意这里的+1 和 -1，可以让我们不用考虑死循环以及左中点，右中点情况。假如我们使用`high = mid`，当low = high的时候，就有可能进入`high = mid`的分支逻辑中，导致无限死循环。
3.  **注意溢出**
    
    在取中间值时，很多人常用`mid = (left + right) / 2`的形式，当left与right数值的加和较大时 ，是有可能溢出Int的取值范围的。可以采用`mid = left + (right - left) / 2`的形式，结果是相同的。在JDK1.8中，采用`(low + high) >>> 1`，>>>是无符号右移，高位自动补0，所以当low + high溢出时变成负数，无符号右移一位又变成了正数。

public int bsearch(int[] a, int n, int value) {
            int low = 0;
            int high = n - 1;
    
            while (low <= high) {
                int mid = (low + high) >>> 1;
                if (a[mid] == value) {
                    return mid;
                } else if (a[mid] < value) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            return -1;
        }

## 变形一：查找第一个等于给定值的元素 ##

与原题区别在于，当a\[mid\] == value时，还需要确认是不是第一个值等于给定值的元素。

当遍历到数组第一个数，或者左边值不同时，必定是第一个，直接返回（此处同时做了溢出校验）

当不是第一个元素时，从右到左收缩区间，继续二分查找。

/**
         * 变形一：
         * 存在重复元素，查找第一个等于给定值的元素
         */
        public int bsearch1(int[] a, int n, int value) {
            int low = 0;
            int high = n - 1;
            while (low <= high) {
                int mid = (low + high) >>> 1;
                if (a[mid] > value) {
                    high = mid - 1;
                } else if (a[mid] < value) {
                    low = mid + 1;
                } else {
                    //此处区别在于，当a[mid]等于需要的值时，还需要确认是不是第一个值等于给定值的元素.当遍历到数组第一个数，或者左边值不同时，必定是第一个，直接返回
                    if ((mid == 0) || (a[mid - 1] != value)) {
                        return mid;
                    } else {
                        high = mid - 1;
                    }
                }
            }
            return -1;
        }

## 变形二：查找最后一个等于给定值的元素 ##

类比变形一，变形一查找的第一个，此处查找的最后一个元素。即需要确认是不是最后一个值等于给定值的元素。

当遍历到数组最后一位，或者右边元素值不等时，必定是最后一个，返回下标。

如果不是最后一个元素，从左到右收缩区间，继续二分查找。

/**
         * 变形二：
         * 查找最后一个值等于给定值的元素
         */
        public int bsearch2(int[] a, int n, int value) {
            int low = 0;
            int high = n - 1;
            while (low <= high) {
                int mid = (low + high) >>> 1;
                if (a[mid] > value) {
                    high = mid - 1;
                } else if (a[mid] < value) {
                    low = mid + 1;
                } else {
                    //此处区别在于，当a[mid]等于需要的值时，还需要确认是不是最后一个值等于给定值的元素.当遍历到数组最后一位，或者右边值不同时，符合要求直接返回
                    if ((mid == n - 1) || (a[mid + 1] != value)) {
                        return mid;
                    } else {
                        low = mid + 1;
                    }
                }
            }
            return -1;
        }

## 变形三：查找第一个大于等于给定值的元素 ##

在变形一基础上，将条件从**查找一个等于定值的元素** 改成 **第一个大于等于定值的元素**，增加了一个大于的判断条件。则代码如下：

/**，
         * 变形三：
         * 查找第一个大于等于给定值的元素
         * 如序列：3，4，6，7，19 查找第一个大于5的元素，即为6
         * 第一个大于给定值，则说明上一个小于给定值，依次判断
         */
        public int bsearch3(int[] a, int n, int value) {
            int low = 0;
            int high = n - 1;
            while (low <= high) {
                int mid = (low + high) >>> 1;
                if (a[mid] >= value) {
                    if ((mid == 0) || (a[mid - 1] < value)) {
                        return mid;
                    } else {
                        high = mid - 1;
                    }
                } else {
                    low = mid + 1;
                }
            }
            return -1;
        }

## 变形四：查找最后一个小于等于给定值的元素 ##

类比上面三题，此处不再赘述。

/**
         * 变形四：
         * 查找最后一个小于等于给定值的元素、
         * 如：3，5，6，8，9，10 最后一个小于7的元素是6
         */
        public int bsearch4(int[] a, int n, int value) {
            int low = 0;
            int high = n - 1;
            while (low <= high) {
                int mid = (low + high) >>> 1;
                if (a[mid] > value) {
                    high = mid - 1;
                } else {
                    if ((mid == n - 1) || (a[mid + 1] > value)) {
                        return mid;
                    } else {
                        low = mid + 1;
                    }
                }
            }
            return -1;
        }

[Git代码地址][Git]

[Git]: https://links.jianshu.com/go?to=%21https%3A%2F%2Fgithub.com%2Ficecrea%2Fleetcode%2Fblob%2Fmaster%2Fsrc%2Fmain%2Fjava%2Fcom%2Fexample%2Fsummary%2Fsortalgorithm%2FBinarySearch.java