写在前
对于二分查找关键是：确定二分查找的搜索区间，下面代码（T704）中数组中元素唯一。不存在返回索引为-1。
class Solution {
// 代码1:搜索区间[l, r)
public int search(int[] nums, int target) {
int l = 0, r = nums.length;
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
r = mid;
} else {
l = mid + 1;
}
}
return -1;
}
// 代码2:搜索区间[l, r]
public int search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return -1;
}
}
如果数组中元素不唯一，我们需要找到重复元素的左右边界（下边有详细题解T34），关键是我们找到目标值，不是选择直接返回它的索引，而是继续向一侧缩小空间（具体哪一侧需要看寻找哪个边界）。
class Solution {
// 代码1:左边界
public int search(int[] nums, int target) {
int l = 0, r = nums.length;
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] < target) {
l = mid + 1;
} else {
// 当找到目标值，我们选择继续缩小左区间
r = mid;
}
}
return l;
}
// 代码2:右边界
public int search(int[] nums, int target) {
int l = 0, r = nums.length;
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] < target) {
r = mid;
} else {
// 当找到目标值，我们选择继续缩小右区间
l = mid + 1;
}
}
return l - 1;
}
}
ps：上述采用左闭右开的写法
- 上述的写法中返回l和r无区别，因为循环的终止条件是 l == r;
- 为什么右边界要减1呢？因为我们对 left 的更新必须是 l = mid + 1，就是说 while 循环结束时，nums[l] 一定不等于 target 了，而 nums[l-1] 可能是 target。
- 对于查找的元素不存在的情况可以单独判断。添加下面代码判断即可：
// 左边界
if (l >= nums.length || nums[l] != target) {
return -1;
}
// 右边界
if (l == 0 || nums[l - 1] != target) {
return -1;
}
1.搜索插入位置（35-易）
题目描述：排序数组中寻找目标值的索引，若不存在目标值，则返回目标值该插入的索引值。
示例：
输入: [1,3,5,6], 5
输出: 2
输入: [1,3,5,6], 7
输出: 4
思路：本题暴力解法为遍历，但由于数组有序(题目假设无重复元素，二分法返回下标唯一)，也可以使用二分法减少时间复杂度，所以有序的数组都可以考虑使用二分查找。
法1.主要判断当前值与目标值大小，相等或者大于目标值，返回当前索引值；小于目标值继续遍历循环。
法2.对于排序数组，我们要想到二分查找，时间复杂度O(logn)，这里主要注意二分法边界的处理（更新区域的边界）！
代码1：暴力遍历
public int searchInsert(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] < target) {
continue;
} else {
// 是否插入在数组最前端
if (i == 0) return 0;
return i;
}
}
return nums.length;
}
代码2：二分查找
public int searchInsert(int[] nums, int target) {
int l = 0, r = nums.length;
while (l < r) { //定义target在左闭右开的区间
int m = l + ((r - l) >> 1);
if (nums[m] > target) {
r = m;
} else if (nums[m] < target) {
l = m + 1;
} else {
return m;
}
}
/**
四种情况：
1.target数组最前端，即[0,0), return 0
2.target等于nums[m], return m
-------------------------------
3.target介于[l, r）之间，return r
4.target在数组末端，return r
**/
return r;
}
2.寻找重复数（287-中）
题目描述：数组元素取值范围[1，n]，假设只有一个重复数（出现两次或多次），找出这个重复数。
进阶问题：
- 如何证明 nums 中至少存在一个重复的数字?
- 你可以在不修改数组 nums 的情况下解决这个问题吗？
- 你可以只用常量级 O(1) 的额外空间解决这个问题吗？
- 你可以设计一个时间复杂度小于 O(n^2) 的解决方案吗？
示例：
输入：nums = [1,3,4,2,2]
输出：2
输入：nums = [3,1,3,4,2]
输出：3
思路：
法1.暴力遍历元素两两比较，实现简单，但时间复杂度O(n^2)；
法2.由于数组元素取值的特殊性，把数组看成链表结构，把寻找重复值看成利用快慢指针寻找链表环的入口；
法3.值域的二分查找。最大值n，最小值1，记录一个变量cnt，统计数组中小于等于mid的个数，根据个数与mid值的大小，二分确定重复值所在区间，时间复杂度O(nlogn)。
代码1：双指针
public int findDuplicate(int[] nums) {
int slow = nums[0], fast = nums[nums[0]];
while (slow != fast) { //1.指针首次相遇退出循环（可能在环中某个位置）
slow = nums[slow];
fast = nums[nums[fast]];
}
fast = 0; //2.快指针移到开始位置
while (slow != fast) { //3.快慢指针每次移动一步，指针再次相遇找到环入口，即重复值
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
代码2：二分查找值域
public int findDuplicate(int[] nums) {
int l = 1, r = nums.length - 1;
while (l < r) {
int mid = l + ((r - l) >> 1);
int cnt = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] <= mid) {
cnt++; //1.每次遍历数组，记录小于mid元素的个数
}
}
if (cnt > mid) { //2.重复值在左区域，mid取大了
r = mid;
} else {
l = mid + 1; //3.重复值在右区域，mid取小了
}
}
return l;
}
3.长度最小的子数组（209-中）
题目描述：返回数组中累加和大于等于给定值的最短连续子数组的长度。要求：时间复杂度O(nlogn)
示例：
输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
思路：涉及连续子数组的问题，通常有两种思路：滑动窗口和前缀和。
法1.滑动窗口，滑动窗口维护了满足要求子数组：窗口右边界更新累加和sum，若满足条件，更新最小长度min，移动窗口的左边界，更新此时sum，遍历数组。
法2.前缀和+二分查找：本题每个元素都为正，保证前缀和一定是递增的（升序）！
空间换时间：为了提高效率，我们创建数组sums来存储前缀和，其中，sums[i]表示从nums[0]到nums[i - 1]的元素和。
目标：sums[k] - sums[i - 1] >= s，k - (i - 1)即满足条件的子数组长度。如何求解最短的呢？将原目标转化一下，即s + sums[i - 1] <= sums[k]，由于sums元素是递增有序的，那么只要求出s + sums[i - 1]，二分查找这个下标K即可。
代码1：滑动窗口
public int minSubArrayLen(int s, int[] nums) {
int l = 0, r = 0;
int sum = 0;
int min = Integer.MAX_VALUE;
while (r < nums.length) {
sum += nums[r++];
//满足条件，找最短的子数组，注意使用while循环！
while (sum >= s) {
min = Math.min(min, r - l);
sum -= nums[l++];
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
代码2：前缀和+二分查找
public int minSubArrayLen(int s, int[] nums) {
int n = nums.length;
if (n == 0) return 0;
int[] sums = new int[n];
sums[0] = nums[0];
for (int i = 1; i < n; i++) {
sums[i] = nums[i] + sums[i - 1];
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
int s2 = s - nums[i];
//二分查找，目标值是 s2 + sums[i]
int k = binarySearch(i, n - 1, sums, s2 + sums[i]);
if (k != -1) {
min = Math.min(min, k - i + 1);
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
// 寻找大于等于 target 所有 sums 中最小的那个
private int binarySearch(int start, int end, int[] sums, int target) {
int mid = -1;
while (start < end) {
mid = (start + end) >>> 1;
if (sums[mid] >= target) {
end = mid;
} else {
start = mid + 1;
}
}
// 没有找到返回 -1
return sums[start] >= target ? start : -1;
}
另解：使用二分查找库函数：如果找到返回下标，如果没有找到就返回一个负数，这个负数取反之后就是原数组中第一个比他大的值的下标（待插入位置）。
public int minSubArrayLen(int s, int[] nums) {
int n = nums.length;
int min = Integer.MAX_VALUE;
int[] sums = new int[n + 1];
for (int i = 1; i <= n; ++i) {
sums[i] = nums[i - 1] + sums[i - 1];
}
for (int i = 0; i <= n; ++i) {
int target = s + sums[i];
int index = Arrays.binarySearch(sums, target);
if (index < 0) index = ~index;
if (index <= n) min = Math.min(min, index - i);
}
return min == Integer.MAX_VALUE ? 0 : min;
}
4.有序矩阵的第K小的元素（378-中）
题目描述：找到方阵（行列元素都是升序）中排序后第k小的元素。
示例：
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
返回 13。
思路：目标：寻找矩阵中第k小的元素
法1.二分查找：类比287解法3。由于矩阵的有序性，可将整个值域进行二分查找。通过计算中间值mid，统计矩阵中小于等于这个值的元素有cnt个，当cnt<k，说明我们中间值取小了，否则，中间值取大了，通过调整值域一步步锁定目标。优化方案即240题思路，改变搜索的起始位置。
ps：为什么l == r返回的数值一定是矩阵中的值呢，首先明确一点我们mid是不一定在矩阵中的，只作为划分值。
假设m为第k小的元素，s为第k + 1个，要使得有k个小于等于mid的元素，那么mid一定介于m和s之间，我们返回的是left，其实就是第一个满足有k个小于等于自身的元素，那么m一定是第一个，所以left一定在矩阵中。
法2.大根堆：维护一个大根堆，当堆的大小>k，就弹出当前值，最后遍历完矩阵，最终堆顶元素就是第k小的元素。注意：优先级队列默认使用小根，效率较低。
代码1：二分查找值域，时间复杂度：O(n^2log(r - l))
public int kthSmallest(int[][] matrix, int k) {
int m = matrix.length, n = matrix[0].length;
int l = matrix[0][0], r = matrix[m - 1][n - 1];
while (l < r) { //第k小的元素一定在[l, r)之间，当l == r，找到第k小元素！！！
int cnt = 0;
int mid = l + ((r - l) >> 1);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n && matrix[i][j] <= mid; j++) {
cnt++; //小于mid的元素个数
}
}
if (cnt < k) { //说明第k小元素在右半部分（mid取小了）
l = mid + 1;
} else {
r = mid;
}
}
return l;
}
优化：利用矩阵的有序性，时间复杂度：O(nlog(r - l))
public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
int left = matrix[0][0], right = matrix[n - 1][n - 1];
while (left < right) {
int mid = left + ((right - left) >> 1);
if (check(matrix, mid, k, n)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
public boolean check(int[][] matrix, int mid, int k, int n) {
int i = n - 1, j = 0;
int cnt = 0;
while (i >= 0 && j < n) {
if (matrix[i][j] <= mid) {
cnt += i + 1;
j++;
} else {
i--;
}
}
return cnt >= k;
}
代码2：堆解法
public int kthSmallest(int[][] matrix, int k) {
Queue<Integer> pq = new PriorityQueue<>((o1, o2) -> o2 - o1);
for (int i = 0; i < matrix.length; ++i) {
for (int j = 0; j < matrix[0].length; ++j) {
pq.add(matrix[i][j]);
if (pq.size() > k) {
pq.poll();
}
}
}
return pq.poll();
}
5.在排序数组中查找元素的第一个和最后一个位置（34-中）
题目描述：给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。要求：时间复杂度O(logn)
示例：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
思路：本题两个关键点是数组有序和时间复杂度要求。所以使用二分查找。
对于二分查找，一定注意区间不变性，下边代码给出的查找区间尾[l, r)，当l == r退出循环。
- 若数组中存在目标值，那么不断缩小查找区间，最终l指向一定是目标值
- 若不存在目标值，那么最终指向第一个满足nums[mid] > target元素
注意：这里为了代码简洁，我们使用一个技巧找右边界，就是找target + 1的左边界，最后我们将找到的索引 - 1就是目标值的右边界了。 对于找到的索引值，检查是否满足条件。
代码：二分查找
public int[] searchRange(int[] nums, int target) {
int first = binarySearch(nums, target);
int last = binarySearch(nums, target + 1) - 1; // 注意这里target不存在也不要紧，最后会在数组中找到比target + 1大的最小值的索引
if (first == nums.length || nums[first] != target) {
return new int[]{-1, -1};
} else {
return new int[]{first, Math.max(first, last)};
}
}
private int binarySearch(int[] nums, int target) {
int l = 0, r = nums.length;
while (l < r) {
int m = l + (r - l) / 2;
if (nums[m] >= target) {
r = m;
} else {
l = m + 1;
}
}
return l;
}
6.在排序数组中查找单一元素（34-中）
题目描述：给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
思路：本题两个关键点是数组有序和时间复杂度要求。所以使用二分查找。本质是通过相邻比较，因为单一元素破坏了有序对，从而确定目标元素的位置。
代码实现：
class Solution {
// 暴力解
public int singleNonDuplicate(int[] nums) {
int n = nums.length;
for (int i = 0; i < n - 1; i += 2) {
if (nums[i] != nums[i + 1]) {
return nums[i];
}
}
return nums[n - 1];
}
// 二分查找（单一元素之后，成对的状态被破坏）
public int singleNonDuplicate(int[] nums) {
int n = nums.length;
int l = 0, r = n - 1;
while (l < r) {
int mid = l + (r - l) / 2;
// l, m 和 r 都应该落在偶数位置
if (mid % 2 == 1) {
mid--;
}
if (nums[mid] == nums[mid + 1]) {
l = mid + 2;
} else {
r = mid;
}
}
return nums[l];
}
// 二分查找优化（mid为奇与左边比较，偶数与右边比较）
public int singleNonDuplicate(int[] nums) {
int n = nums.length;
int l = 0, r = n - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] == nums[mid ^ 1]) {
l = mid + 1;
} else {
r = mid;
}
}
return nums[l];
}
}
7.在排序数组中查找单一元素（34-中）
题目描述：给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
思路：参考@Terry2020，本题转化一下就是有序数组寻找第k小的数。
递归出口：当K=1时候，相当于求最小值，我们只要比较nums1和nums2的起始位置i和j上的数字就可以了。
一般情况：取两个数组中的第k/2个元素（midVal1和midVal2）进行比较，如果midVal1 < midVal2，则说明数组1中的前k/2个元素不可能成为第k个元素的候选，所以将数组1中的前k/2个元素去掉，作为新数组和数组2求第k-k/2小的元素，因为我们把前k/2个元素去掉了，所以相应的k值也应该减少k/2。midVal1 > midVal2的情况亦然。
-
边界问题：
- 当某一个数组的起始位置大于等于其数组长度时，说明其所有数字均已经被淘汰了，相当于一个空数组了，那么实际上就变成了在另一个数组中找数字，直接就可以找出来了。
- 由于两个数组的长度不定，所以有可能某个数组元素数不足k/2，所以我们需要先检查一下，数组中到底存不存在第K/2个数字，如果存在就取出来，否则就赋值上一个整型最大值，这样肯定会大于另一个数组的第k/2个元素，从而把另一个数组的前k/2个元素淘汰。
ps：赋予整型最大值的意思只是说如果第一个数组的K/2不存在，则说明这个数组的长度小于K/2，那么另外一个数组的前K/2个我们是肯定不要的。例如，加入第一个数组长度是2，第二个数组长度是12，则K为7，K/2为3，因为第一个数组长度小于3，则无法判断中位数是否在其中，而第二个数组的前3个肯定不是中位数！
使用一个小trick，可以避免讨论奇偶：我们分别找第 (m+n+1)/2个数，和(m+n+2)/2个数，然后求其平均值即可，这对奇偶数均适用。假如 m+n 为奇数的话，那么其实 (m+n+1) / 2 和 (m+n+2) / 2 的值相等，相当于两个相同的数字相加再除以2，还是其本身。
代码实现：
class Solution {
// 暴力解：时间复杂度O(m + n) 空间复杂度O(m + n)
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int[] mergeArray = new int[m + n];
int index = 0;
int i = 0, j = 0;
while (i < m && j < n) {
mergeArray[index++] = nums1[i] > nums2[j] ? nums2[j++] : nums1[i++];
}
while (i < m) {
mergeArray[index++] = nums1[i++];
}
while (j < n) {
mergeArray[index++] = nums2[j++];
}
int midIdx = m + n >> 1;
return (m + n) % 2 == 1 ? (double) mergeArray[midIdx] :
((double) mergeArray[midIdx] + (double) mergeArray[midIdx - 1]) / 2;
}
// 二分查找（寻找第k小的数）
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
// 寻找中位数
int left = (m + n + 1) / 2;
int right = (m + n +2) / 2;
return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
}
/**
findKth:两个有序数组找第k个元素
i:nums1的起始位置
j:nums2的起始位置
*/
private int findKth(int[] nums1, int i, int[] nums2, int j, int k) {
if (j == nums2.length) {
return nums1[i + k - 1];
}
if (i == nums1.length) {
return nums2[j + k - 1];
}
// 递归出口
if (k == 1) {
return Math.min(nums1[i], nums2[j]);
}
// 找这两个数组的第k/2小的数字，不足K/2个数字，赋值整形最大值，以便淘汰另一个数组的前K/2个数字
int midVal1 = (i + k/2 - 1) < nums1.length ? nums1[i + k/2 - 1] : Integer.MAX_VALUE;
int midVal2 = (j + k/2 - 1) < nums2.length ? nums2[j + k/2 - 1] : Integer.MAX_VALUE;
// 核心逻辑
if (midVal1 < midVal2) {
return findKth(nums1, i + k/2, nums2, j, k - k/2);
} else {
return findKth(nums1, i, nums2, j + k/2, k - k/2);
}
}
}
8.在排序数组中查找单一元素（34-中）
思路分析：由于调用次数限制，并且数组在山顶的两边严格的升序或者降序。所以可以使用二分查找：
- 二分查找找到峰顶索引
- 分别对左右两边进行二分查找（技巧：利用flag标记升序还是降序）
代码实现：
/**
* // This is MountainArray's API interface.
* // You should not implement it, or speculate about its implementation
* interface MountainArray {
* public int get(int index) {}
* public int length() {}
* }
*/
class Solution {
public int findInMountainArray(int target, MountainArray mountainArr) {
int n = mountainArr.length();
int l = 0, r = n - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (mountainArr.get(mid) <mountainArr.get(mid + 1)) {
l = mid + 1;
} else {
r = mid;
}
}
int index = binarySearch(target, mountainArr, 0, l, true);
return index != -1 ? index : binarySearch(target, mountainArr, l + 1, n - 1, false);
}
public int binarySearch(int target, MountainArray mountainArr, int l, int r, boolean flag) {
while (l <= r) {
int mid = l + (r - l) / 2;
if (mountainArr.get(mid) == target) {
return mid;
}
if (mountainArr.get(mid) < target) {
l = flag ? mid + 1 : l;
r = flag ? r : mid - 1;
} else {
r = flag ? mid - 1 : r;
l = flag ? l : mid + 1;
}
}
return -1;
}
}
