关于java:面试前必知必会的二分查找及其变种

须要更多算法动图详解，能够微信搜寻 [袁厨的算法小屋]

明天给大家带来的是二分查找及其变种的总结，大家肯定要看到最初呀，用心满满，废话不多说，让导演帮咱们把镜头切到袁记菜馆吧！

袁记菜馆内。。。。

店小二：掌柜的，您进货回来了呀，哟！明天您买这鱼挺大呀！

袁厨：那是，这是我明天从咱们江边买的，之前始终去菜市场买，那里的老贵了，你猜猜我明天买的多少钱一条。

店小二：之前的鱼，30 个铜板一条，明天的我猜 26 个铜板。

袁厨：贵了。

店小二：还贵呀！那我猜 20 个铜板！

袁厨：还是贵了。

店小二：15 个铜板。

袁厨：便宜了

店小二：18 个铜板

袁厨：祝贺你猜对了

下面的例子就用到了咱们的二分查找思维，如果你玩过相似的游戏，那二分查找了解起来必定很轻松啦，上面咱们一起驯服二分查找吧！

二分查找

二分查找也称折半查找（Binary Search），是一种在有序数组中查找某一特定元素的搜索算法。咱们能够从定义可知，使用二分搜寻的前提是数组必须是有序的，这里须要留神的是，咱们的输出不肯定是数组，也能够是数组中某一区间的起始地位和终止地位

通过下面二分查找的定义，咱们晓得了二分查找算法的作用及要求，那么该算法的具体执行过程是怎么的呢？

上面咱们通过一个例子来帮忙咱们了解。咱们须要在 nums 数组中，查问元素 8 的索引

int[]  nums = {1,3,4,5,6,8,12,14,16}; target = 8  

（1）咱们须要定义两个指针别离指向数组的头部及尾部，这是咱们在整个数组中查问的状况，当咱们在数组

某一区间进行查问时，能够输出数组，起始地位，终止地位进行查问。

（2）找出 mid，该索引为 mid =（left + right）/ 2，然而这样写有可能溢出，所以咱们须要改良一下写成

mid = left +（right – left）/ 2 或者 left + ((right – left) >> 1) 两者作用是一样的，都是为了找到两指针的中

间索引，应用位运算的速度更快。那么此时的 mid = 0 + (8-0) / 2 = 4

（3）此时咱们的 mid = 4，nums[mid] = 6 < target, 那么咱们须要挪动咱们的 left 指针，让 left = mid + 1，下次则能够在新的 left 和 right 区间内搜寻目标值，下图为挪动前和挪动后

（4）咱们须要在 left 和 right 之间计算 mid 值，mid = 5 +（8 – 5）/ 2 = 6 而后将 nums[mid] 与 target 持续比拟，进而决定下次挪动 left 指针还是 right 指针，见下图

（5）咱们发现 nums[mid] > target，则须要挪动咱们的 right 指针，则 right = mid – 1；则挪动过后咱们的 left 和 right 会重合，这里是咱们的一个重点大家须要留神一下，前面会对此做具体叙述。

（6）咱们须要在 left 和 right 之间持续计算 mid 值，则 mid = 5 +（5 – 5）/ 2 = 5，见下图，此时咱们将 nums[mid] 和 target 比拟，则发现两值相等，返回 mid 即可，如果不相等则跳出循环，返回 -1。

二分查找的执行过程如下

1. 从曾经排好序的数组或区间中，取出两头地位的元素，将其与咱们的目标值进行比拟，判断是否相等，如果相等

则返回。

2. 如果 nums[mid] 和 target 不相等，则对 nums[mid] 和 target 值进行比拟大小，通过比拟后果决定是从 mid

的左半局部还是右半局部持续搜寻。如果 target > nums[mid] 则右半区间持续进行搜寻，即 left = mid + 1; 若

target < nums[mid] 则在左半区间持续进行搜寻，即 right = mid -1；

动图解析

上面咱们来看一下二分查找的代码，能够认真思考一下 if 语句的条件，每个都没有简写。

 public static int binarySearch(int[] nums,int target,int left, int right) {
        // 这里须要留神，循环条件
        while (left <= right) {
            // 这里须要留神，计算 mid
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) {return mid;}else if (nums[mid] < target) {
                // 这里须要留神，挪动左指针
                left  = mid + 1;
            }else if (nums[mid] > target) {
                // 这里须要留神，挪动右指针
                right = mid - 1;
            }
        }
        // 没有找到该元素，返回 -1
        return -1;
    }

二分查找的思路及代码曾经了解了，那么咱们来看一下实现时容易出错的中央

1. 计算 mid 时，不能应用（left + right）/ 2, 否则有可能会导致溢出

2.while (left < = right) {} 留神括号内为 left <= right , 而不是 left < right，咱们持续回顾方才的例子，如果咱们设置条件为 left < right 则当咱们执行到最初一步时，则咱们的 left 和 right 重叠时，则会跳出循环，返回 -1，区间内不存在该元素，然而不是这样的，咱们的 left 和 right 此时指向的就是咱们的指标元素，然而此时 left = right 跳出循环

3.left = mid + 1,right = mid – 1 而不是 left = mid 和 right = mid。咱们思考一下这种状况, 见下图，当咱们的 target 元素为 16 时，而后咱们此时 left = 7，right = 8，mid = left + (right – left) = 7 + (8-7) = 7，那如果设置 left = mid 的话，则会进入死循环，mid 值始终为 7。

上面咱们来看一下二分查找的递归写法

public static int binarySearch(int[] nums,int target,int left, int right) {if (left <= right) {int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) {
                // 查找胜利
                return  mid;
            }else if (nums[mid] > target) {
                // 新的区间, 左半区间
                return binarySearch(nums,target,left,mid-1);
            }else if (nums[mid] < target) {
                // 新的区间，右半区间
                return binarySearch(nums,target,mid+1,right);
            }
        }
        // 不存在返回 -1
        return -1;
    }

例题：

题目形容

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按程序插入的地位。

你能够假如数组中无反复元素。

示例 1:

输出: [1,3,5,6], 5
输入: 2

示例 2:

输出: [1,3,5,6], 2
输入: 1

示例 3:

输出: [1,3,5,6], 7
输入: 4

示例 4:

输出: [1,3,5,6], 0
输入: 0

题目解析

这个题目齐全就和咱们的二分查找一样，只不过有了一点改写，那就是将咱们的返回值改成了 left，具体实现过程见下图

class Solution {public int searchInsert(int[] nums, int target) {

        int left = 0, right = nums.length-1;
        // 留神循环条件
        while (left <= right) {
            // 求 mid
            int mid = left + ((right - left) >> 1);
            // 查问胜利
            if (target == nums[mid]) {
                return mid;
            // 右区间    
            } else if (nums[mid] < target) {
                left = mid + 1;   
            // 左区间               
            } else if (nums[mid] > target) {right = mid - 1;}
        }
        // 返回插入地位
        return left;
    }
}

二分查找变种一

下面咱们说了如何应用二分查找在数组或区间里查出特定值的索引地位。然而咱们方才数组外面都没有反复值，查到返回即可，那么咱们思考一下上面这种状况

此时咱们数组里含有多个 5，咱们查问是否含有 5 能够很容易查到，然而咱们想获取第一个 5 和 最初一个 5 的地位应该怎么实现呢？哦！咱们能够应用遍历，当查问到第一个 5 时，咱们设立一个指针进行定位，而后达到最初一个 5 时返回，这样咱们就能求的第一个和最初一个五了？因为咱们这个文章的主题就是二分查找，咱们可不可以用二分查找来实现呢？当然是能够的。

题目形容

给定一个依照升序排列的整数数组 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]

题目解析

这个题目很容易了解，咱们在下面说了如何应用遍历解决该题，然而这个题目的目标就是让咱们应用二分查找，咱们来一一剖析，先找出指标元素的下边界，那么咱们如何找到指标元素的下边界呢？

咱们来重点剖析一下方才二分查找中的这段代码

  if (nums[mid] == target) {return mid;}else if (nums[mid] < target) {
      // 这里须要留神，挪动左指针
      left  = mid + 1;
  }else if (nums[mid] > target) {
      // 这里须要留神，挪动右指针
      right = mid - 1;
  } 

咱们只需在这段代码中批改即可，咱们再来分析一下这块代码，nums[mid] == target 时则返回，nums[mid] < target 时则挪动左指针，在右区间进行查找，nums[mid] > target 时则挪动右指针，在左区间内进行查找。

那么咱们思考一下，如果此时咱们的 nums[mid] = target , 然而咱们不能确定 mid 是否为该指标数的左边界，所以此时咱们不能够返回下标。例如上面这种状况。

此时 mid = 4，nums[mid] = 5, 然而此时的 mid 指向的并不是第一个 5，所以咱们须要持续查找，因为咱们要找

的是数的下边界，所以咱们须要在 mid 的值的左区间持续寻找 5，那咱们应该怎么做呢？咱们只需在

target <= nums[mid] 时，让 right = mid – 1 即可，这样咱们就能够持续在 mid 的左区间持续找 5。是不是听着有点绕，咱们通过上面这组图进行形容。

其实原理很简略，就是咱们将小于和等于合并在一起解决，当 target <= nums[mid] 时，咱们都挪动右指针，也就是 right = mid -1，还有一个须要留神的就是，咱们计算下边界时最初的返回值为 left，当上图完结循环时，left = 3，right = 2，返回 left 刚好时咱们的下边界。咱们来看一下求下边界的具体执行过程。

动图解析

计算下边界代码

int lowerBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            // 这里须要留神，计算 mid
            int mid = left + ((right - left) >> 1);
            if (target <= nums[mid]) {// 当目标值小于等于 nums[mid] 时，持续在左区间检索，找到第一个数
                right = mid - 1;

            }else if (target > nums[mid]) {// 目标值大于 nums[mid] 时，则在右区间持续检索，找到第一个等于目标值的数
                left = mid + 1;

            }
        }
        return left;
    }

计算上边界时算是和计算上边界时条件相同，

计算下边界时，当 target <= nums[mid] 时，right = mid -1；target > nums[mid] 时，left = mid + 1；

计算上边界时，当 target < nums[mid] 时，right = mid -1; target >= nums[mid] 时 left = mid + 1; 刚好和计算下边界时条件相同，返回 right。

计算上边界代码

int upperBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            // 求 mid
            int mid = left + ((right - left) >> 1);
            // 挪动左指针状况
            if (target >= nums[mid]) {
                 left = mid + 1; 
            // 挪动右指针状况
            }else if (target < nums[mid]) {right = mid - 1;}
            
        }
        return left;
    }

题目残缺代码

class Solution {public int[] searchRange (int[] nums, int target) {int upper = upperBound(nums,target);
         int low = lowerBound(nums,target);  
         // 不存在状况
         if (upper < low) {return new int[]{-1,-1};
         }
         return new int[]{low,upper};
    }
    // 计算下边界
    int lowerBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            // 这里须要留神，计算 mid
            int mid = left + ((right - left) >> 1);
            if (target <= nums[mid]) {// 当目标值小于等于 nums[mid] 时，持续在左区间检索，找到第一个数
                right = mid - 1;

            }else if (target > nums[mid]) {// 目标值大于 nums[mid] 时，则在右区间持续检索，找到第一个等于目标值的数
                left = mid + 1;

            }
        }
        return left;
    }
    // 计算上边界
    int upperBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {int mid = left + ((right - left) >> 1);
            if (target >= nums[mid]) {left = mid + 1;}else if (target < nums[mid]) {right = mid - 1;}            
        }
        return right;
    }
}

二分查找变种二

咱们在下面的变种中，形容了如何找出指标元素在数组中的高低边界，而后咱们上面来看一个新的变种，如何从数组或区间中找出第一个大于或最初一个小于指标元素的数的索引，例 nums = {1,3,5,5,6,6,8,9,11} 咱们心愿找出第一个大于 5 的元素的索引，那咱们须要返回 4，因为 5 的前面为 6，第一个 6 的索引为 4，如果心愿找出最初一个小于 6 的元素，那咱们则会返回 3，因为 6 的后面为 5 最初一个 5 的索引为 3。好啦题目咱们曾经理解，上面咱们先来看一下如何在数组或区间中找出第一个大于指标元素的数吧。

找出第一个大于指标元素的数，大略有以下几种状况

1. 数组蕴含指标元素，找出在他前面的第一个元素

2. 指标元素不在数组中，数组内的局部元素大于它，此时咱们须要返回第一个大于他的元素

3. 指标元素不在数组中，且数组中的所有元素都大于它，那么咱们此时返回数组的第一个元素即可

4. 指标元素不在数组中，且数组中的所有元素都小于它，那么咱们此时没有查问到，返回 -1 即可。

既然咱们曾经剖析完所有状况，那么这个题目对咱们就没有难度了，上面咱们形容一下案例的执行过程

nums = {1,3,5,5,6,6,8,9,11} target = 7

下面的例子中，咱们须要找出第一个大于 7 的数，那么咱们的程序是如何执行的呢？

下面的例子咱们曾经弄懂了，那么咱们看一下，当 target = 0 时，程序应该怎么执行呢？

OK! 咱们到这一步就能把这个变种给整的明明白白的了，上面咱们看一哈程序代码吧，也是非常简单的。

public static int lowBoundnum(int[] nums,int target,int left, int right) {while (left <= right) {
            // 求两头值
            int mid = left + ((right - left) >> 1);
            // 大于目标值的状况
            if (nums[mid] > target) {
                 // 返回 mid
                if (mid == 0 || nums[mid-1] <= target) {return mid;}
                else{right = mid -1;}

            } else if (nums[mid] <= target){left = mid + 1;}
        }
        // 所有元素都小于指标元素
        return -1;
    }

通过下面的例子咱们应该能够齐全了解了那个变种，上面咱们持续来看以下这种状况，那就是如何找到最初一个小于指标数的元素。还是下面那个例子

nums = {1,3,5,5,6,6,8,9,11} target = 7

查找最初一个小于指标数的元素，比方咱们的指标数为 7，此时他后面的数为 6，最初一个 6 的索引为 5，此时咱们返回 5 即可，如果指标数元素为 12，那么咱们最初一个元素为 11，仍小于指标数，那么咱们此时返回 8，即可。这个变种其实算是下面变种的相同状况，下面的会了，这个也齐全能够搞定了，上面咱们看一下代码吧。

public static int upperBoundnum(int[] nums,int target,int left, int right) {while (left <= right) {int mid = left + ((right - left) >> 1);
             // 小于目标值
            if (nums[mid] < target) {
                // 看看是不是以后区间的最初一位，如果以后小于，前面一位大于，返回以后值即可
                if (mid == right || nums[mid+1] >= target) {return mid;}
                else{left = mid + 1;}

            } else if (nums[mid] >= target){right = mid - 1;}
        }
        // 没有查问到的状况
        return -1;
    }

哎嘛写着写着咋就那么多了，太长了大家就不爱看啦，剩下的就放在下篇吧，咱们下篇见呀！

如果这篇文章对您有一丢丢帮忙的话，或者是能感触到这篇文章的用心的话，那么感谢您的点赞，在看，转发呀，这样我就满血复活啦。

我是袁厨，一个热爱用动图解算法的年轻人，一个热爱做饭的程序员，一个想和你一起提高的小老弟。