二分查找
二分查找是很有技巧的算法, 只有大约有 20% 的程序员能正确地解释一个二分查找的正确性;
很多细节值得考量:
怎样计算 mid 不会数值溢出
m = l + (r-l)/2mid 偏向左边还是右边
根据需要控制, 求左边界就偏向左边, 求右边界就偏向右边
while 的判断条件用不用
=缩小范围的解法不能用
=, 严格加减的解法可以用=求边界时如何在迭代中更新范围
m 偏左让
r = m, m 偏右让l = m最后需不需要验证相等
循环条件不用
=的, 必须验证初始化边界需不需要+1
无所谓, 最后验证即可
直接找值
最简单的
704. 二分查找 easy
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
class Solution {
public int search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l <= r) {
int m = l + (r - l >> 1);
if (nums[m] == target)
return m;
else if (nums[m] < target)
l = m + 1;
else
r = m - 1;
}
return -1;
}
}边界
34. 在排序数组中查找元素的第一个和最后一个位置 mid
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
m 偏左, 左边界+1; m 偏右, 右边界-1;
class Solution {
public int[] searchRange(int[] nums, int target) {
if (nums.length == 0) return new int[]{-1, -1};
int tl = -1, tr = -1;
int l = 0, h = nums.length - 1;
// [)
while (l < h) {
int m = l + (h - l >> 1);
if (nums[m] < target) l = m + 1;
else h = m;
}
if (nums[l] != target) return new int[]{-1, -1};
tl = l;
// (]
h = nums.length - 1;
while (l < h) {
int m = l + (h - l + 1 >> 1);
if (nums[m] > target) h = m - 1;
else l = m;
}
tr = h;
return new int[]{tl, tr};
}
}35. 搜索插入位置 easy
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
找 >= target 的左边界, 注意需要初始化 r=length
class Solution {
public int searchInsert(int[] nums, int target) {
int l = 0, r = nums.length;
while (l < r) {
int m = l + (r - l >> 1);
if (nums[m] < target) l = m + 1;
else r = m;
}
return l;
}
}278. 第一个错误的版本 easy
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。 假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
/*
The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version);
*/
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int l = 1, r = n;
while (l < r) {
int m = l + (r - l >> 1);
if (isBadVersion(m)) r = m;
else l = m + 1;
}
return r;
}
}540. 有序数组中的单一元素 mid
剑指 Offer II 070. 排序数组中只出现一次的数字
给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。 请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
解法
索引中有一个分隔, 左边 [偶数]=[偶数+1], 右边 [奇数]=[奇数+1]
class Solution {
public int singleNonDuplicate(int[] nums) {
int l = 0, h = nums.length - 1;
while (l < h) {
int m = l + (h - l >> 1);
// i:i^1 奇数 i:i-1 偶数 i:i+1
if (nums[m] == nums[m ^ 1]) l = m + 1;
else h = m;
}
return nums[l];
}
}744. 寻找比目标字母大的最小字母 easy
给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。
class Solution {
public char nextGreatestLetter(char[] letters, char target) {
int l = 0, h = letters.length;
while (l < h) {
int m = l + (h - l >> 1);
if (letters[m] > target) h = m;
else l = m + 1;
}
return l == letters.length ? letters[0] : letters[l];
}
}旋转数组
33. 搜索旋转排序数组 mid
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
解法
根据 nums[0] 判断 m 在左还是右, 然后缩小范围找 target
class Solution {
public int search(int[] nums, int target) {
int l = 0, h = nums.length - 1;
while (l <= h) {
int m = l + (h - l >> 1);
if (target == nums[m]) return m;
// 左
if (nums[m] >= nums[0]) {
if (target < nums[0]) l = m + 1;
else {
if (target < nums[m]) h = m - 1;
else l = m + 1;
}
}
// 右
else {
if (target >= nums[0]) h = m - 1;
else {
if (target > nums[m]) l = m + 1;
else h = m - 1;
}
}
}
return -1;
}
}func search(nums []int, target int) int {
l := 0
r := len(nums) - 1
for l < r {
m := l + (r-l)>>1 // go的操作符优先级不同
if target == nums[m] {
return m
}
// 左
if nums[m] >= nums[0] {
switch {
case target > nums[m]:
l = m + 1
case target < nums[0]:
l = m + 1
default:
r = m - 1
}
// 右
} else {
switch {
case target < nums[m]:
r = m - 1
case target >= nums[0]:
r = m - 1
default:
l = m + 1
}
}
}
// 这里跟循环条件是对应的:
// 循环中如果使用缩小范围的方式, 则循环条件必须是 l<r, 则此步是必须的;
// 循环中如果使用严格加减的方式, 则循环条件可以是 l<=r, 此步可以省略;
if nums[l] == target {
return l
}
return -1
}也可以使用边界查找
class Solution {
public int search(int[] nums, int target) {
int l = 0, h = nums.length - 1;
while (l < h) {
int m = l + (h - l >> 1);
// m 在左
if (nums[0] <= nums[m]) {
// target 在右
if (target < nums[0]) l = m + 1;
// target 在 m 左
else {
if (target <= nums[m]) h = m;
// target 在 m 右
else l = m + 1;
}
}
// m 在右
else {
// target 在左
if (target >= nums[0]) h = m - 1;
// target 在 m 右
else {
if (target <= nums[m]) h = m;
// target 在 m 左
else l = m + 1;
}
}
}
return nums[l] == target ? l : -1;
}
}153. 寻找旋转排序数组中的最小值 mid
已知一个长度为 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) 的算法解决此问题。
如果 mid 比 h 小, 说明在同一段; 否则不在同一段
class Solution {
public int findMin(int[] nums) {
// 大=>最大 最小=>大 3 4 5 0 1 2
int l = 0, h = nums.length - 1;
while (l < h) {
int m = l + (h - l >> 1);
if (nums[m] <= nums[h]) h = m;
else l = m + 1;
}
return nums[l];
}
}154. 寻找旋转排序数组中的最小值 II hard
剑指 Offer 11. 旋转数组的最小数字 easy
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
- 若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
- 若旋转 7 次，则可以得到 [0,1,4,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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。
你必须尽可能减少整个过程的操作步骤。
如果 mid 比 h 小, 说明在同一段; 否则不在同一段
有重复元素, [m]!=[h] 的没影响; 相等的要判断, 最小值可能藏匿在中间, 例如 3 3 1 3
class Solution {
public int findMin(int[] nums) {
int l = 0;
int h = nums.length - 1;
while (l < h) {
int m = l + (h - l) / 2;
if (nums[m] < nums[h]) h = m;
else if (nums[m] > nums[h]) l = m + 1;
// -= 1
else h--;
}
return nums[l];
}
}水平对称单调区间
852. 山脉数组的峰顶索引 mid
符合下列属性的数组 arr 称为 山脉数组 ：
- arr.length >= 3
- 存在 i（0 < i< arr.length - 1）使得：
- arr[0] < arr[1] < ... arr[i-1] < arr[i]
- arr[i] > arr[i+1] > ... > arr[arr.length - 1]
给你由整数组成的山脉数组 arr，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int l = 1, h = arr.length - 1;
while (l < h) {
int m = l + (h - l >> 1);
if (arr[m] < arr[m + 1]) l = m + 1;
else h = m;
}
return l;
}
}