二分查找二分边界查找算法的模板代码总结KeepCoding

一般而言，当一个题目出现以下特性时，你就应该立即联想到它可能需要使用二分查找：

二分查找有很多种变体，使用时需要注意查找条件，判断条件和左右边界的更新方式，三者配合不好就很容易出现死循环或者遗漏区域，本篇中我们将介绍常见的几种查找方式的模板代码，包括：

本文的内容来自于笔者个人的总结，事实上二分查找有很多种等价的写法，本文只是列出了笔者认为的最容易理解和记忆的方法。

首先给出标准二分查找的模板：

classBinarySearch{publicintsearch(int[]nums,inttarget){intleft=0;intright=nums.length-1;while(left<=right){intmid=left+((right-left)>>1);if(nums[mid]==target)returnmid;elseif(nums[mid]>target){right=mid-1;}else{left=mid+1;}}return-1;}}这里有几点需要注意：

即因为mid对于长度为偶数的区间总是偏左的，所以当区间长度小于等于2时，mid总是和left在同一侧。

Ipickanumberfrom1ton.YouhavetoguesswhichnumberIpicked.

Everytimeyouguesswrong,I'lltellyouwhetherthenumberishigherorlower.

Youcallapre-definedAPIguess(intnum)whichreturns3possibleresults(-1,1,or0):

-1:Mynumberislower1:Mynumberishigher0:Congrats!Yougotit!Example:

Input:n=10,pick=6Output:6

这题基本是可以直接照搬二分查找的，出题者没有做任何包装，我们直接使用标准二分查找：

publicclassSolutionextendsGuessGame{publicintguessNumber(intn){intleft=1;intright=n;while(left<=right){intmid=left+((right-left)>>1);if(guess(mid)==0){returnmid;}elseif(guess(mid)==-1){right=mid-1;}else{left=mid+1;}}return-1;}}实战2：Sqrt(x)Implementintsqrt(intx).Computeandreturnthesquarerootofx,wherexisguaranteedtobeanon-negativeinteger.Sincethereturntypeisaninteger,thedecimaldigitsaretruncatedandonlytheintegerpartoftheresultisreturned.这一题其实是二分查找的应用，乍一看好像和二分查找没有关系，但是我们可以用二分查找的思想快速定位到目标值的平方根，属于二分查找的一个简单运用：

classSolution{publicintmySqrt(intx){if(x<=1)returnx;intleft=1;intright=x-1;while(left<=right){intmid=left+((right-left)>>1);if(mid>x/mid){right=mid-1;}elseif(midx/(mid+1))returnmid;left=mid+1;}else{returnmid;}}return-1;//onlyforreturnavalue}}虽然是简单的题目，但是还是要注意对溢出的处理，例如我们使用mid>x/mid而不是mid*mide>x作为判断条件，因为后者可能会导致溢出，这与我们使用left+((right-left)>>1)而不是(left+right)/2作为mid的值是一个道理，这是因为left+right也可能溢出。

利用二分法寻找左边界是二分查找的一个变体，应用它的题目常常有以下几种特性之一：

类型1包括了上面说的第一种，第二种情况。

既然要寻找左边界，搜索范围就需要从右边开始，不断往左边收缩，也就是说即使我们找到了nums[mid]==target,这个mid的位置也不一定就是最左侧的那个边界，我们还是要向左侧查找，所以我们在nums[mid]偏大或者nums[mid]就等于目标值的时候，继续收缩右边界，算法模板如下：

classSolution{publicintsearch(int[]nums,inttarget){intleft=0;intright=nums.length-1;while(left

首先，这里的右边界的更新是right=mid，因为我们需要在找到目标值后，继续向左寻找左边界。

其次，这里的循环条件是left

事实上，我们只需要遍历到left和right相邻的情况就行了，因为这一轮循环后，无论怎样，left,mid,right都会指向同一个位置，而如果这个位置的值等于目标值，则它就一定是最左侧的目标值；如果不等于目标值，则说明没有找到目标值，这也就是为什么返回值是nums[left]==targetleft:-1。

左边界查找的第二种类型用于数组部分有序且包含重复元素的情况，这种条件下在我们向左收缩的时候，不能简单的令right=mid，因为有重复元素的存在，这会导致我们有可能遗漏掉一部分区域，此时向左收缩只能采用比较保守的方式，代码模板如下：

classSolution{publicintsearch(int[]nums,inttarget){intleft=0;intright=nums.length-1;while(lefttarget){right=mid;}else{right--;}}returnnums[left]==targetleft:-1;}}它与类型1的唯一区别就在于对右侧值的收缩更加保守。这种收缩方式可以有效地防止我们一下子跳过了目标边界从而导致了搜索区域的遗漏。

关于这种类型的例子，可以看下面的实战5。

这道题的题目比较长，原题就不贴了，大意就是说：有这么一个数组：

[false,false,false,...,fasle,true,true,...,true]求最左侧的那个true的位置。

这就是一个典型的查找左边界的问题：数组中包含重复元素，我们需要找到最左侧边界的位置。直接使用二分查找左边界的模板就行了：

(i.e.,[0,1,2,4,5,6,7]mightbecome[4,5,6,7,0,1,2]).

Findtheminimumelement.

Youmayassumenoduplicateexistsinthearray.

这一题看上去没有重复元素，但是它也是查找左边界的一种形式，即可以看做是查找旋转到右侧的部分的左边界，有了这个思想，直接用二分查找左边界的模板就行了：

classSolution{publicintfindMin(int[]nums){if(nums.length==1)returnnums[0];intleft=0;intright=nums.length-1;while(left>1);if(nums[mid]>nums[nums.length-1]){left=mid+1;}else{right=mid;}}returnnums[left];}}实战5：FindMinimuminRotatedSortedArrayII这道题目和上面的实战2类似，只是多了一个条件——数组中可能包含重复元素，这就是我们之前说的二分查找左边界的第二种类型，在这种情况下，我们只能采用保守收缩的方式，以规避重复元素带来的对于单调性的破坏：

classSolution{publicintfindMin(int[]nums){if(nums.length==1)returnnums[0];intleft=0;intright=nums.length-1;while(left>1);if(nums[mid]>nums[right]){//mid位于旋转点左侧left=mid+1;}elseif(nums[mid]

classSolution{publicintsearch(int[]nums,inttarget){intleft=0;intright=nums.length-1;while(left>1)+1;if(nums[mid]>target){right=mid-1;}else{left=mid;}}returnnums[right]==targetright:-1;}}这里大部分和寻找左边界是对称着来写的，唯独有一点需要尤其注意——中间位置的计算变了，我们在末尾多加了1。这样，无论对于奇数还是偶数，这个中间的位置都是偏右的。

对于这个操作的理解，从对称的角度看，寻找左边界的时候，中间位置是偏左的，那寻找右边界的时候，中间位置就应该偏右呗，但是这显然不是根本原因。根本原因是，在最后left和right相邻时，如果mid偏左，则left,mid指向同一个位置，right指向它们的下一个位置，在nums[left]已经等于目标值的情况下，这三个位置的值都不会更新，从而进入了死循环。所以我们应该让mid偏右，这样left就能向右移动。这也就是为什么我们之前一直强调查找条件，判断条件和左右边界的更新方式三者之间需要配合使用。

右边界的查找一般来说不会单独使用，如有需要，一般是需要同时查找左右边界。

前面我们介绍了左边界和右边界的查找，那么查找左右边界就容易很多了——只要分别查找左边界和右边界就行了。

这是一道特别标准的查找左右边界的题目，我们只需要分别查找左边界和右边界就行了：

classSolution{publicint[]searchRange(int[]nums,inttarget){int[]res=newint[]{-1,-1};if(nums==null||nums.length==0)returnres;//findtheleft-endintleft=0;intright=nums.length-1;while(left>1);if(nums[mid]>1)+1;if(nums[mid]>target){right=mid-1;}else{left=mid;}}res[1]=right;}}returnres;}}二分查找极值二分查找还有一种有趣的变体是二分查找极值点，之前我们使用nums[mid]去比较的时候，常常是和给定的目标值target比，或者和左右边界比较，在二分查找极值点的应用中，我们是和相邻元素去比，以完成某种单调性的检测。关于这一点，我们直接来看一个例子就明白了。

这一题的有趣之处在于他要求求一个局部极大值点，并且整个数组不包含重复元素。所以整个数组甚至可以是无序的——你可能很难想象我们可以在一个无序的数组中直接使用二分查找，但是没错！我们确实可以这么干！谁要人家只要一个局部极大值即可呢。

classSolution{publicintfindPeakElement(int[]nums){intleft=0;intright=nums.length-1;while(left>1);if(nums[mid]

除了本文所介绍的二分查找的应用方式，二分查找其实还有很多其他的变体和应用，但它们基本上是循环条件，判断条件，边界更新方法的不同组合，例如，有的二分查找的循环条件可以是while(left+1

但是无论如何，代码模板只是给大家一个理解问题的角度，生搬硬套总是不好的。实际应用中，我们只要记住循环条件，判断条件与边界更新方法三者之间的配套使用就行了，基于这一点原则，你就可以使用你自己习惯的方式来实现二分搜索。

但是，如果你真的只是想应付面试，我想下面这个表的总结应该就差不多足够用了：

最后，希望大家在理解二分查找的思想后都能够写出适合自己的搭配方式，共勉！