以第一题为例，介绍二分查找的两种写法：闭区间和左闭右开区间（后边的题均为左闭右开写法）
一、搜索插入位置
简单
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4提示:
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4nums为 无重复元素 的 升序 排列数组-10^4 <= target <= 10^4
1.1 闭区间 [l，r]
class Solution {
/**
* 35. 搜索插入位置（闭区间）
*
* @param nums 提供的数组
* @param target 目标查找元素
* @return 目标元素应在位置的索引
*/
public int searchInsert(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (nums[m] < target) l = m + 1;
else r = m - 1;
}
return l;
}
}执行用时0ms，击败100.00%，复杂度O(logN)
消耗内存44.20MB，击败5.73%，复杂度O(1)
1.2 左闭右开 [l，r)
class Solution {
/**
* 35. 搜索插入位置（左闭右开）
*
* @param nums 提供的数组
* @param target 目标查找元素
* @return 目标元素应在位置的索引
*/
public int searchInsert(int[] nums, int target) {
int l = 0, r = nums.length;
while (l < r) {
int m = l + (r - l) / 2;
if (nums[m] < target) l = m + 1;
else r = m;
}
return l;
}
}二、搜索二维矩阵
中等
给你一个满足下述两条属性的 m x n 整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-10^4 <= matrix[i][j], target <= 10^4
2.1 两次二分查找
思路不难想：
先对行进行二分查找，锁定目标元素出现的行
锁定完后就变成了一维数组的二分查找
class Solution {
/**
* 74. 搜索二维矩阵（两次二分查找）
*
* @param matrix 提供的数组
* @param target 目标查找元素
* @return 目标元素是否存在
*/
public boolean searchMatrix(int[][] matrix, int target) {
int ri = matrix.length - 1, rj = matrix[0].length - 1;
if (target > matrix[ri][rj]) return false;
int li = 0, lj = 0;
if (target < matrix[li][lj]) return false;
while (li <= ri) {
int mi = li + (ri - li) / 2;
if (matrix[mi][0] <= target) li = mi + 1;
else ri = mi - 1;
}
li--;
while (lj <= rj) {
int mj = lj + (rj - lj) / 2;
if (matrix[li][mj] < target) lj = mj + 1;
else rj = mj - 1;
}
if (lj >= matrix[0].length) return false;
return matrix[li][lj] == target;
}
}2.2 一次二分查找
如果能把二维映射成一维数组，那么只需要一次二分查找即可
int i = mid / n, j = mid % n;
例如一个3 * 5的二维数组，数字11应该对应哪个地方？
从左往右从上到下应该是[0, 1, 2, 3, 4]、[5, 6, 7, 8, 9]、[10, 11, …]，即11 ÷ 5 = 2 ······ 1
class Solution {
/**
* 74. 搜索二维矩阵（一次二分查找）
*
* @param matrix 提供的数组
* @param target 目标查找元素
* @return 目标元素是否存在
*/
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
if (target < matrix[0][0] || matrix[m - 1][n - 1] < target) return false;
int l = 0, r = m * n;
while (l < r) {
int mid = l + (r - l) / 2;
int i = mid / n, j = mid % n;
if (matrix[i][j] < target) l = mid + 1;
else r = mid;
}
return matrix[l / n][l % n] == target;
}
}三、在排序数组中查找元素的第一个和最后一个位置
中等
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 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]提示：
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9nums是一个非递减数组-10^9 <= target <= 10^9
3.1 二分查找后中心扩散
第一思路不难想，先二分查找找到目标值，然后以找到的这个目标值为中心，向左和向右遍历即可
class Solution {
/**
* 34. 在排序数组中查找元素的第一个和最后一个位置（二分查找后中心扩散）
*
* @param nums 提供的数组
* @param target 目标查找元素
* @return 目标元素存在的区间
*/
public int[] searchRange(int[] nums, int target) {
if (nums.length == 0) return new int[]{-1, -1};
int l = 0, r = nums.length;
while (l < r) {
int m = l + (r - l) / 2;
if (target > nums[m]) l = m + 1;
else r = m;
}
if (l >= nums.length || nums[l] != target) return new int[]{-1, -1};
while (l >= 0 && nums[l] == target) l--;
while (r < nums.length && nums[r] == target) r++;
return new int[]{l + 1, r - 1};
}
}但是如果在nums[]恒为2，而目标值是2时，该方法的时间复杂度会变成O(N)
那么二分查找出来的这个扩散中心，他会落在哪里呢？是左边界，右边界，还是区间内的随机一个数
3.2 两次二分查找
3.1中二分查找找到的是左边界
看 if 语句的 = 判断是移动哪个指针
- 如果移动的是左指针，说明固定的是右边界，查找到的就是右边界
- 如果移动的是右指针，说明固定的是左边界，查找到的就是左边界
while (l < r) {
int m = l + (r - l) / 2;
if (target > nums[m]) l = m + 1;
else r = m; // 这里是target <= nums[m]，所以是左边界
}class Solution {
/**
* 34. 在排序数组中查找元素的第一个和最后一个位置（两次二分查找）
*
* @param nums 提供的数组
* @param target 目标查找元素
* @return 目标元素存在的区间
*/
public int[] searchRange(int[] nums, int target) {
if (nums.length == 0) return new int[]{-1, -1};
int l0 = 0, r0 = nums.length;
while (l0 < r0) {
int m = l0 + (r0 - l0) / 2;
if (target > nums[m]) l0 = m + 1;
else r0 = m;
}
if (l0 >= nums.length || nums[l0] != target) return new int[]{-1, -1};
int l1 = 0, r1 = nums.length;
while (l1 < r1) {
int m = l1 + (r1 - l1) / 2;
if (target >= nums[m]) l1 = m + 1;
else r1 = m;
}
return new int[]{l0, l1 - 1};
}
}四、搜索旋转排序数组
中等
整数数组 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) 的算法解决此问题。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1示例 3：
输入：nums = [1], target = 0
输出：-1提示：
1 <= nums.length <= 5000-10^4 <= nums[i] <= 10^4nums中的每个值都 独一无二- 题目数据保证
nums在预先未知的某个下标上进行了旋转 -10^4 <= target <= 10^4
4.1 两“个”二分查找
注意到整个数组原先是递增的，旋转过后，以旋转中心点隔开的左右区间内，数据也都是单调递增的
/ /
/ => /
/ /可以发现，左区间的数 >= 右区间的数
即：left_min >= right_max，其中left_min = nums[0], right_max = nums[nums.length - 1]
∴ 于是可以先判断target和right_max的大小：
right_max >= target，说明目标值在右侧区间内- 反之在左侧区间内
因此，我们用两种不同的二分查找逻辑来实现：
searchL（搜索左区间）- 如果中点
nums[mid] <= right_max，说明当前区间中点落在右侧区间，不是答案区间，直接将右边界推到mid的位置 - 反之，说明当前区间中点落在左侧区间内，执行正常的二分查找逻辑
- 如果中点
searchR（搜索右区间）- 与
searchL的大体逻辑相近
- 与
以下采用左闭右开的写法：
class Solution {
/**
* 33. 搜索旋转排序数组（两个二分查找）
*
* @param nums 提供的数组
* @param target 目标查找元素
* @return 目标元素的位置
*/
public int search(int[] nums, int target) {
int end = nums.length - 1;
if (nums[end] >= target) return searchR(nums, target);
else return searchL(nums, target);
}
private int searchL(int[] nums, int target) {
int length = nums.length;
int l = 0, r = length;
while (l < r) {
int m = l + (r - l) / 2;
// 如果区间中点落在右侧递增区域
if (nums[m] <= nums[length - 1]) r = m;
else {
if (nums[m] < target) l = m + 1;
else r = m;
}
}
if (l == length) return -1;
return nums[l] == target ? l : -1;
}
private int searchR(int[] nums, int target) {
int length = nums.length;
int l = 0, r = length;
while (l < r) {
int m = l + (r - l) / 2;
// 如果区间中点落在左侧递增区域
if (nums[m] > nums[length - 1]) l = m + 1;
else {
if (nums[m] < target) l = m + 1;
else r = m;
}
}
if (l == length) return -1;
return nums[l] == target ? l : -1;
}
}五、寻找旋转排序数组中的最小值
中等
已知一个长度为 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) 的算法解决此问题。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。示例 3：
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。提示：
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums中的所有整数 互不相同nums原来是一个升序排序的数组，并进行了1至n次旋转
5.1 一次二分查找
说是旋转可能看不懂，用人话解释一下
旋转 n ：将整个数组向右移动 n 次
示例：12345 -> 旋转1 = 向右移动1 -> 51234
由 4.1 两“个”二分查找
可以发现，左区间的数 >= 右区间的数
即：
left_min >= right_max，其中left_min = nums[0], right_max = nums[nums.length - 1]
不断判断区间中点在哪一边：
- 在左边，将左边界推到
mid + 1 - 在右边，将右边界推到
mid
当l = r，循环结束，此时指向的就是最小值
class Solution {
/**
* 153. 寻找旋转排序数组中的最小值（二分查找）
*
* @param nums 提供的数组
* @return 数组最小值
*/
public int findMin(int[] nums) {
int end = nums[nums.length - 1];
int l = 0, r = nums.length;
while (l < r) {
int m = l + (r - l) / 2;
// 如果区间中点落在左侧递增区域
if (nums[m] > end) l = m + 1; // 推动左边界
else r = m; // 否则推右边界
}
if (l == nums.length) return end;
return nums[l];
}
}六、寻找两个正序数组的中位数
困难
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5提示：
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-10^6 <= nums1[i], nums2[i] <= 10^6
6.1 二分查找
- 两个数组合并后的中位数，会把合并后的数组分成两部分：
L = (m + n + 1) / 2个数 <= 中位数，剩下的数 >= 中位数- 因此，对于两个分开的数组，用 mid1 和 mid2 去切分数组 nums1 和 nums2，有
mid1 + mid2 = L - ∴
mid2 = L - mid1 - 👇红色的是
L部分的数字
- 因此，对于两个分开的数组，用 mid1 和 mid2 去切分数组 nums1 和 nums2，有
- 只要保证左半部分（红色区域）的最大值 ≤ 右半部分（蓝色区域）的最小值，中位数即可由这两个端点直接得到
- 先令
m <= n，在较短的数组 nums1 上二分次数更少，用 mid2=L−mid1 补齐另一个切分
定义（基于切分 mid1 与 mid2）
- l1：nums1 左半部分的最后一个元素（mid1−1），如果 mid1==0，则视为负无穷
- r1：nums1 右半部分的第一个元素（mid1），如果 mid1==m，则视为正无穷
- l2：nums2 左半部分的最后一个元素（mid2−1），如果 mid2==0，则视为负无穷
- r2：nums2 右半部分的第一个元素（mid2），如果 mid2==n，则视为正无穷
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
if (m > n) return findMedianSortedArrays(nums2, nums1);
int L = (m + n + 1) / 2; // 全部数字左半边的总数
int lm = 0, rm = m + 1;
while (lm < rm) {
int mm = lm + (rm - lm) / 2; // mid1
int mn = L - mm; // mid2
int l1 = (mm == 0) ? Integer.MIN_VALUE : nums1[mm - 1];
int r1 = (mm == m) ? Integer.MAX_VALUE : nums1[mm];
int l2 = (mn == 0) ? Integer.MIN_VALUE : nums2[mn - 1];
int r2 = (mn == n) ? Integer.MAX_VALUE : nums2[mn];
// 只要保证左半部分（红色区域）的最大值 ≤ 右半部分（蓝色区域）的最小值
// 中位数即可由这两个端点直接得到
if (l1 <= r2 && l2 <= r1) {
int lMax = Math.max(l1, l2);
int rMin = Math.min(r1, r2);
if ((m + n) % 2 == 1) return lMax;
return (lMax + rMin) / 2.0;
} else if (l1 > r2) {
rm = mm; // mid1 太大了，缩右边界到 mm
} else if (l2 > r1) {
lm = mm + 1; // mid1 太小了，扩左边界到 mm + 1
}
}
return 0.0; // 不会执行到这里
}
}