目录​​​​​​​

9.1 搜索插入位置（简单）：二分查找

9.2 搜索旋转排序数组(中等)：二分查找

9.3 搜索旋转排序数组Ⅱ（中等）：二分查找

9.4 搜索二维矩阵（中等）：二分查找

9.5 寻找旋转排序数组中的最小值（中等）：二分查找（这个有点绕）

9.6 x的平方根（简单）：二分查找

9.7 寻找峰值（中等）：二分查找

9.8 二分法总结！！！

9.1 搜索插入位置（简单）：二分查找

题目：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。

思想：在一个排序数组中寻求目标值，利用二分法就能正好满足复杂度需求，但该题需要返回不存在数组中值的对应索引，因此需要特殊处理：

  • 若插入位置为pos，则：nums[pos - 1] < target < nums[pos]

  • 最终left的值就是我们需要求得的应该插入的位置或者就是目标值

总结：要能够清晰的理解题意

代码：

class Solution {public int searchInsert(int[] nums, int target) {//设置二分法的左右指针int left = 0;int right = nums.length - 1;​//二分查找步骤：左指针小于右指针的情况下循环while(left <= right){//中间值的求法int middle = left + (right - left) / 2;//左右指针移动if(nums[middle] < target){left = middle + 1; }else{right = middle - 1; } }//最终索引值就是left；return left; }}

9.2 搜索旋转排序数组(中等)：二分查找

题目：整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

思想：原本的数组是升序排列，经过旋转之后，则这道题中给定的数组可以从中心分为两部分，这两部分一定有一部分是有序的，比如: [4,5,6,7,0,1,2] ，,从middle分开为：[4, 5, 6] 和 [7, 0, 1, 2] 两个部分，其中左边 [4, 5, 6] 这个部分的数组是有序的，然后在使用二分查找

  • 由middle分开为两个部分 [l, mid] 和 [mid + 1, r] ，我们查看target位于哪个区间内，然后再在该区间内查找值即可

总结：将旋转后数组从middle分为两部分，然后判断target的位置

代码：

class Solution {public int search(int[] nums, int target) {//若数组为空，直接返回-1if(nums == null || nums.length == 0){return -1; }//若数组只有一个值，直接判断if(nums.length == 1){return target == nums[0] ? 0 : -1; }​//声明左右指针int left = 0;int right = nums.length - 1;​//进行二分查找while(left <= right){int middle = left + (right - left) / 2;​if(nums[middle] == target){return middle; }//若目标值在左区间if(nums[0] <= nums[middle]){if(nums[0] <= target && target <= nums[middle]){right = middle - 1; }else{left = middle + 1; } }//若目标在右区间else{if(nums[middle] < target && target <= nums[nums.length - 1]){left = middle + 1; }else{right = middle - 1; } } }return -1; }}​//暴力解法public int search(int[] nums, int target) {int i = 0;for (int num : nums) {if (num == target) {return i; }i++; }return -1; }

9.3 搜索旋转排序数组Ⅱ（中等）：二分查找

题目：已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

你必须尽可能减少整个操作步骤。

思想：不要为了二分查找而进行二分查找，可以存在更优解

总结：要能够清晰的理解题意

代码：

class Solution {public boolean search(int[] nums, int target) {for(int v : nums){if(v == target){return true; } }return false; }}

9.4 搜索二维矩阵（中等）：二分查找

题目：给你一个满足下述两条属性的 m x n 整数矩阵：

  • 每行中的整数从左到右按非递减顺序排列。

  • 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

思想：将矩阵合并看作为一个升序数组，然后对升序数组进行二分查找

  • 我们需要确定的是矩阵中第(i, j)个位置上是否存在target，因此将每次(i, j)位置的值和target相比较即可，若存在相等值说明就存在

  • 我们可以发现：数组第(i, j)位置的值可以这样取得：nums[middle / n][midlle % n]；

  • 进行二分查找时，我们直接比较(i, j)的值和target大小即可，根据大小移动左右指针，可以将此时的(i, j)当作是一个middle

总结：将矩阵合并为一个升序数组后对应索引的位置求法是很巧妙的，可以多在纸上进行数学验证得出

代码：

class Solution {public boolean searchMatrix(int[][] matrix, int target) {//得到数组的长与宽int m = matrix.length;int n = matrix[0].length;​//声明矩阵合并为升序数组后的左右指针int low = 0;int high = m * n - 1;​//进行二分查找while(low <= high){int middle = low + (high - low) / 2;//矩阵中任意一个元素的值可以表示为：`nums[middle / n][midlle % n]`int x = matrix[middle / n][middle % n];//比较当前值和target的大小，若当前值小，由于数组升序，将左指针右移if(x  target){high = middle - 1; }else{return true; } }return false; }}

9.5 寻找旋转排序数组中的最小值（中等）：二分查找（这个有点绕）

题目：已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

  • 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]

  • 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

思想：一个升序数组经过旋转后，我们可以发现旋转后的数组的最后一个元素x和数组的最小值min存在一定关系：

  • min右侧的值一定小于x

  • min左侧的值一定大于x

通过这一点，运用二分查找可以得出：

  • 若nums[middle] < x，说明最小值在middle的左边，可以直接忽略二分查找的右半区间；注意此时应该为：

     if(nums[middle] <= nums[high]){high = middle; }

    • 因为可能middle值就是目标值，若为high = middle - 1;就少了一个值

  • 若nums[middle] > x，说明最小值在middle的右边，可以直接忽略二分查找的左半区间

总结：注意到舍去左右区间时的操作，可以举特例理解

代码：

class Solution {public int findMin(int[] nums) {//声明左右指针int low = 0;int high = nums.length - 1;​//进行二分查找while(low < high){int middle = low + (high - low) / 2;//此时，说明最小值位于middle的左边，忽略右边区间if(nums[middle] <= nums[high]){high = middle; }else{low = middle + 1; } }return nums[low]; }}

9.6 x的平方根（简单）：二分查找

题目：给你一个非负整数 x ，计算并返回 x 的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

思想：只需在小于x的范围之内寻找相乘小于等于x的最大值即可，使用二分查找

总结：注意middle * middle可能会大于int的默认范围，需要将其转为long

代码：

class Solution { public int mySqrt(int x) { int low = 0; int high = x; int res = 0;​ while(low <= high){ int middle = low + (high - low) / 2; if((long)middle * middle <= x){ res = middle; low = middle + 1; }else{ high = middle - 1; } } return res; }}

9.7 寻找峰值（中等）：二分查找

题目：峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

思想：最大值一定是一个峰值，因此直接寻找最大值即可

总结：最大值一定是峰值，可将该题转换思路进行解决

代码：

class Solution {public int findPeakElement(int[] nums) {int low = 0;int high = nums.length - 1;​while(low < high){int middle = low + (high - low) / 2;if(nums[middle] <= nums[middle + 1]){low = middle + 1; }else{high = middle; } }return low; }}

9.8 二分法总结！！！

二分法说到底是可能是一个经典的套路框架，但有时候并不容易，当使用二分法求解时，有几点需要极其注意：

  1. 比较左右指针的大小是 < 还是 <=，这个要根据题目要求，判断左右边界能否达到相同值

  2. 左指针left = middle + 1 或者是 left = middle：这是左边界问题，我们在使用二分法求解时，要根据情况，判断左边界的left值是否需要留到下一次二分时使用

  3. 右指针right= middle - 1 或者是 right= middle：这是右边界问题，同样需要根据情况判断有边界的值是否需要留到下一次二分时使用