二分算法刷题

1 初识

总结：二分算法题的细节非常多，容易写出死循环。使用算法的条件不一定是数组有序，而是具有“二断性”；模板三种后面会讲。

• 朴素二分
• 二分查找左端点
• 二分查找右端点

2 朴素二分

题目链接：[704 二分查找 - 力扣（LeetCode）]( search/description/ “704. 二分查找 - 力扣（LeetCode）”) 循序渐进，先从暴力解法说起。

1. 暴力解法：遍历全部数组，判断是否==target。时间复杂度O（n）。但是这里没有把数组是有序的这个条件给用上。
2. 二分查找算法： “二段性”，当我们发现：我们发现一个规律，在选择一个状态的时候，能够直接丢弃掉“一半”的情况。 只要选取的位置能够将全部情况划分为两个情况就可以，可以是二分之一点，要和可以是三分之一点。 但是从概率上来讲，还是每次选取二分之一点的效率最好。 编写代码 class Solution { public int search(int[] nums, int target) { int left = 0; int right = nums.length -1; while(left <= right){ int mid = left + (right - left) / 2; if(nums[mid] < target) left = mid + 1; else if (nums[mid] > target) right = mid - 1; else return mid; } return -1; } } 朴素二分模板 朴素二分求mid的时候使用（ left + right）/ 2 还是使用（left + right + 1）/2都是一样的

3 在排序数组中查找元素的第一个位置和最后一个位置。（查找区间左端点、右端点）

题目链接：[34 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）]( element-in-sorted-array/description/ “34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）”)

3.1. 暴力解法

遍历查找，第一次遇到这target标记下标，然后继续往后遍历，直到第一次找到大于target的下标。

3.2. 二分

暴力算法同样没有使用数组是有序的这个重要条件。 先来看看朴素二分能不能解决问题？ 是不能的，朴素二分只能保证找到target，但是并不能保证找到的index就是边界啊。 因此就引出了另外两种二分：查找左端点、查找右端点的二分。

3.2.1. 查找左端点

朴素二分是将数组划分成3个状态（大于的、小于的、等于的）。 而查找左端点的时候是不可以将数组划分为三个状态的，这是因为的等于状态的位置请不确定，需要将其和大于状态划分到一起，这个等于的点，有可能刚好就是我们要找的左端点。 这样划分之后， 如果mid落在了【小于target】的这一段区间中，我们的mid该怎么更新状态呢？由于这里已经小于了target，而我们的目标是找到target的左端点，所以mid = mid+1. 如果mid落在了【大于等于target】这一段的区间中，mid则 mid = right，这是因为right很有可能就是我们想要寻找的左端点，不可以跳过。 那么循环的条件是什么？ 无论是【】区间中有结果，还是区间中所有的数字都大于target，或者是小于target，最终，当最终left和right重合的时候，都不需要到循环中再次判断了，这就是最终状态，只需要判断这个时候的left是不是等于target即可。 如果当left==right时候，在进入循环就会陷入死循环。 求mid的操作是什么？ 这里是求左端点，所以mid = （right - left ）/ 2；或者 mid = left + （right-left） /2; 如果使用 mid = left +(right - left + 1) / 2;也会死循环

3.2.2. 查找右端点

原理同上。注意二段性 的运用

3.2.3. 代码

class Solution { public int[] searchRange(int[] nums, int target) { if(nums.length == 0) return new int[]{-1 ,-1}; int[] ret = new int[2]; int left = findLeft(nums,target); int right = findRight(nums,target); ret[0] = left; ret[1] = right; return ret; } private static int findLeft(int[] nums , int target){ int left = 0 , right = nums.length - 1; int mid = 0; while(left < right){ mid = left + (right - left) / 2; if(nums[mid] < target) left = mid + 1; else right = mid; } if(nums[left] != target) return -1; else return left; } private static int findRight(int[] nums , int target){ int left = 0 , right = nums.length - 1; int mid = 0; while(left < right){ mid = left + (right - left + 1) / 2; if(nums[mid] <= target) left = mid ; else right = mid -1; } if(nums[left] != target) return -1; else return right; } }

3.2.4. 模板

不要死记硬背！理解 记住：就中间坐标的方式，其他的可以关联记忆！（分析二段性 – > 分析求中点mid应该怎么求（当下面出现剑法，求mid就有+1；反之则反）），具体的分类讨论的代码，就题论题。分析好中点落在某个区间的时候，left、以及right如何变化。

4 x的平方根

题目链接：

4.1. 暴力解法

从1开始，一次遍历，计算ii 和 x的大小。 这个大小具体满足什么要求？来看题目，题目要求返回的是整数，小数部分就会被舍去。也就是找到最大的i，满足ii <= x.

4.2. 二分

暴力解法中其实已经看到了 二段性，在计算ii的时候，如果不能满足要求，就可以直接排除掉“另一半”的数据量。从上面的分析也可以很清楚的看到，我们需要寻找的就是“满足条件”的数据的右端点。也就是找到 **找到最大的i，满足ii <= x.** 进入循环的条件：while（left < right） 求mid的方式 ： mid = left + （right -left + 1）/ 2； 开始二分 if （ii <= x）left = mid；（因为求的是 右端点，这里有可能是等于的情况，也就是右端点，因此不可以left = mid + 1）. if （iI > x） right = mid -1; (这里已经大于了，不可能包含我们需要的数据) 代码 class Solution { public int mySqrt(int x) { if (x == 0 || x == 1) return x; long left = 1, right = x; long mid; while(left < right){ mid = left + (right - left + 1) / 2; if(mid * mid <= x) left = mid; else right = mid -1; } return (int)left; } }

5 搜索插入顺序

题目链接： [35 搜索插入位置 - 力扣（LeetCode）]( position/description/ “35. 搜索插入位置 - 力扣（LeetCode）”)

5.1. 暴力解法

遍历数组，找到第一个等会或者大于target的数字，返回其下标。

5.2. 二分

实际上就是适用二分法求取区间的左端点，该区间是大于等于target的这个区间。 进入循环的条件 while（left< right） 求mid = left+（right - left） / 2； if（nums[i] < target）left = mid+1; 该区间没有满足的情况，直接跳出； if（nums[i] >= target) right = mid; 该区间有可能，存在【左端点】，也就是恰好nums[i] == target. 结束循环后。left=right，需要判断这时候是存在nums[left] == target,还是不存在，需要返回插入的下标（此时，nunms[left] < target,返回left+1） 代码： class Solution { public int searchInsert(int[] nums, int target) { int left = 0 , right = nums.length - 1; while(left < right){ int mid = left + (right - left) / 2; if(nums[mid] < target) left = mid + 1; else right = mid; } if(nums[left] < target) return left + 1; return left; } }

6 山脉数组的峰值

题目链接：[852 山脉数组的峰顶索引 - 力扣（LeetCode）]( in-a-mountain-array/ “852. 山脉数组的峰顶索引 - 力扣（LeetCode）”)

6.1. 暴力解法

遍历数组中的元素，逐一判断该值是否是【峰值】，峰值的话就是大于前驱，同时也大于后继。

6.2. 二分

这道题目的难点在于，如何能看出来使用二分。 前面说过，二分的题目是看数据的二段性，这道题目的二段性在哪里？ class Solution { public int peakIndexInMountainArray(int[] arr) { int left = 0, right = arr.length - 1; while(left < right){ int mid = left + (right - left ) / 2; if(arr[mid] < arr[mid + 1]) left = mid + 1; else right = mid; } return left; } }

7 搜索旋转排序数组中的最小值

题目链接：[153 寻找旋转排序数组中的最小值 - 力扣（LeetCode）]( minimum-in-rotated-sorted-array/description/ “153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）”)

7.1. 暴力解法

遍历数组，通过比较记录数组中的最小元素，得到的就是最小值。 此时，并没有使用到数组的特殊性质，该数组使用过升序数组“旋转”得到的。

7.2. 二分

为什么能使用二分？ 代码： public int findMin(int[] nums) { int left = 0, right = nums.length - 1; while (left < right) { int mid = left + (right - left) / 2; // 如果中间元素大于右边界元素，说明最小值在右半部分 if (nums[mid] > nums[right]) { left = mid + 1; } else { // 否则，最小值在左半部分或是mid本身 right = mid; } } return nums[left]; }