二分法模板
模板1
模板1的退出条件为i <= j，也就是说循环结束的下方i > j。
public static int search(int[] arr, int target) {
int i = 0, j = arr.length - 1;
while (i <= j) { // 退出条件为i > j
int m = i + ((j - i) >> 1);
if (arr[m] == target) {
return m;
}
if (arr[m] > target) {
j = m - 1;
} else {
i = m + 1;
}
}
// now, i == j + 1
return -1;
}
复制代码x的平方根
题目：计算并返回x的平方根，x是非负整数，结果只保留小数部分。
这道题的返回值不存在-1的情况。
- 使用上面的模板，右端点j从x/2+1开始；
- 没有return m，循环终止时i > j，由于只保留小数部分，所以最终返回j，j接近并略小于x的平方根。
class Solution {
public int mySqrt(int x) {
int i = 0, j = x / 2 + 1;
while (i <= j) {
int m = i + ((j - i) >> 1);
if ((long) m * m == x) {
return m;
}
if ((long) m * m > x) {
j = m - 1;
} else {
i = m + 1;
}
}
return j;
}
}
复制代码搜索旋转排序数组（leetcode 33）
题目：在没有重复数字的升序旋转数组中寻找指定数字，找不到返回-1。
思路：找到中间数后，如果它不是target，那么需要根据中间数与边沿数的大小关系来在哪个区间继续搜索。
- 中间数与左端点比较
class Solution {
public int search(int[] nums, int target) {
int i = 0, j = nums.length - 1;
while (i <= j) {
int m = i + ((j - i) >> 1);
if (nums[m] == target) {
return m;
}
if (nums[m] == nums[i]) { // 中间数等于左端点，即 i == m == j - 1
i++;
} else if (nums[m] > nums[i]) { // 左半区间有序
if (target >= nums[i] && target < nums[m]) { // 在左半区间
j = m - 1;
} else { // 在右半区间
i = m + 1;
}
} else if (nums[m] < nums[i]) { // 右半区间有序
if (target > nums[m] && target < nums[i]) { // 在右半区间
i = m + 1;
} else { // 在左半区间
j = m - 1;
}
}
}
return -1;
}
}
复制代码- 中间数与右端点比较
class Solution {
public int search(int[] nums, int target) {
int i = 0, j = nums.length - 1;
while (i <= j) {
int m = i + ((j - i) >> 1);
if (nums[m] == target) {
return m;
}
if (nums[m] == nums[j]) { // 中间数等于右端点，即i == j == m，可以直接return -1;
j--;
} else if (nums[m] > nums[j]) { // 左半区间有序
if (target >= nums[i] && target < nums[m]) { // 在左半区间
j = m - 1;
} else { // 在右半区间
i = m + 1;
}
} else { // nums[m] < nums[j] 右半区间有序
if (target > nums[m] && target <= nums[j]) { // 在右半区间
i = m + 1;
} else { // 在左半区间
j = m - 1;
}
}
}
return -1;
}
}
复制代码模板2
使用此模板时，有时候不会有target，而是利用中间值和旁边的值或者左右端点值来比较。
public static int search(int[] arr, int target) {
int i = 0, j = arr.length - 1;
while (i < j) {
int m = i + ((j - i) >> 1);
if (arr[m] == target) {
return m;
}
if (arr[m] < target) {
i = m + 1;
} else {
j = m; // 保留略大于target的元素
}
}
// do something
}
复制代码寻找旋转排序数组中的最小值(leetcode 153)
题目：在一个元素互不相同的旋转数组中，寻找最小值。
思路：利用中间值和右端点进行比较，逐步缩小查找范围。
旋转数组存在两种情况，旋转0次和旋转0次以上，例如：
[1, 2, 3, 4, 5] – 旋转0次
[5, 1, 2, 3, 4] – 旋转1次
[4, 5, 1, 2, 3] – 旋转2次
[3, 4, 5, 1, 2] – 旋转3次
[2, 3, 4, 5, 1] – 旋转4次
当中间值和左端点比较时，由于存在旋转0次，最小值的区间是不能确定的
当中间值和右端点比较时， nums[m] < nums[j]最小值在左区间(j = m)，nums[m] > nums[j]最小值在右区间(i = m + 1)。
- 和右端点比较
class Solution {
public int findMin(int[] nums) {
int i = 0, j = nums.length - 1;
while (i < j) {
int m = i + ((j - i) >> 1);
if (nums[m] == nums[j]) { // i == j == m
return nums[m];
}
if (nums[m] > nums[j]) { // 最小值在右边
i = m + 1;
} else { // nums[m] < nums[j] 最小值在左边，且不排除是nums[m]
j = m;
}
}
return nums[i];
}
}
复制代码- 和左端点比较
若要和左端点比较，需要排除旋转0次的情况。初始时旋转了多次的数组在循环的过程中，可能出现旋转0次的形式。因此要放在循环中排除，即根据nums[i]与nums[j]的大小情况来判断。
class Solution {
public int findMin(int[] nums) {
int i = 0, j = nums.length - 1;
while (i < j) {
int m = i + (j - i) / 2;
// 排除旋转0次的情况
if (nums[i] < nums[j]) {
return nums[i];
}
if (nums[m] == nums[i]) { // m == i == j - 1
return nums[j]; // 上面已经消除了旋转0次的情况，此处必有nums[i] > nums[j]，因此返回nums[j]。
}
if (nums[m] < nums[i]) {
j = m;
} else { // nums[m] > nums[i]
i = m + 1;
}
}
return nums[i];
}
}
复制代码模板3
这三个模板的主要区别是while条件不同，在while循环代码块中，可以使用的元素范围也不同。对于模板3，在循环中，可以使用i、i+1、i+2三个位置上的元素。
退出循环后，i+1==j，剩下i、j两个位置上的元素。
public static int search(int[] arr, int target) {
int i = 0, j = arr.length - 1;
while (i + 1 < j) {
int m = i + ((j - i) >> 1);
if (arr[m] == target) {
return m;
}
if (arr[m] < target) {
i = m;
} else {
j = m; // 保留略大于target的元素
}
}
// do something
}
复制代码旋转数组问题汇总
33 搜索旋转排序数组
模板1中已解决。
81 搜索旋转排序数组 II
与33不同的是，数组中元素可以重复。结果返回true/false。
10.03. 搜索旋转数组
与81类似，但结果要返回相等且索引最小的那个。
153 寻找旋转排序数组中的最小值
模板2中已解决。
154 寻找旋转排序数组中的最小值 II
与153不同的是，数组中元素可以重复。
搜索旋转排序数组 II
直接和没有重复元素的代码一模一样，只有返回值变为了true/false。
下面用的是中间值和右端点比较
class Solution {
public boolean search(int[] nums, int target) {
int i = 0, j = nums.length - 1;
while (i <= j) {
int m = i + ((j - i) >> 1);
if (nums[m] == target) {
return true;
}
if (nums[m] == nums[j]) {
j--;
} else if (nums[m] > nums[j]) {
if (target >= nums[i] && target < nums[m]) {
j = m - 1;
} else {
i = m + 1;
}
} else { // nums[m] < nums[j]
if (target > nums[m] & target <= nums[j]) {
i = m + 1;
} else {
j = m - 1;
}
}
}
return false;
}
}
复制代码搜索旋转数组
此题的代码与上题类似，但是当中间值等于target时不能直接返回，而是要搜索左边区间，以取得更小的索引。而这也导致循环终止的条件不能是i <= j，因为当arr[j]等于target且j==i+1时，循环无法终止。
另外，若数组两侧出现相同值，在第一次确定区间的时候可能会去索引较大的区间搜索，所以在循环结束后对此情况进行判断。
而在子区间中是不会出现区间两侧有相同值的情况的，所以循环内的代码逻辑与前面两个搜索旋转数组的题一样。
class Solution {
public int search(int[] arr, int target) {
int i = 0, j = arr.length - 1;
while (i < j) {
int m = i + ((j - i) >> 1);
if (arr[m] == target) {
j = m;
} else {
if (arr[m] == arr[j]) {
j--;
} else if (arr[m] > arr[j]) {
if (target >= arr[i] && target < arr[m]) {
j = m - 1;
} else {
i = m + 1;
}
} else { // arr[m] < arr[j]
if (target > arr[m] && target <= arr[j]) {
i = m + 1;
} else {
j = m - 1;
}
}
}
}
if (arr[i] == target) {
if (arr[0] == arr[i]) {
return 0;
} else {
return i;
}
}
return -1;
}
}
复制代码寻找旋转排序数组中的最小值 II
与I的代码逻辑类似。本题中元素可以重复，当中间数与右端点相等时，无法确定区间，而区间中已经有了nums[m]这个值，所以可以把边上的nums[j]去掉不会排出最小值，还可以缩小范围。
class Solution {
public int findMin(int[] nums) {
int i = 0, j = nums.length - 1;
while (i < j) {
int m = i + ((j - i) >> 1);
if (nums[m] == nums[j]) {
j--;
} else if (nums[m] > nums[j]) {
i = m + 1;
} else { // nums[m] < nums[j]
j = m;
}
}
return nums[i];
}
}
复制代码总结
搜索旋转数组的题目分为2类：
- 搜索旋转数组中的指定值
- 搜索旋转数组中的最小值
另外，元素是否重复在元素不重复的写法上略有修改，不影响代码框架。
可以统一用中间值和右端点比较。
分类讨论时，分大于小于等于，比合并大于等于或小于等于思路更清晰。
![[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/4d3cf227a85d7e79f5d6b4efb6bde3e8.jpg)
![[桜井宁宁] 爆乳奶牛少女cos写真-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/d40483e126fcf567894e89c65eaca655.jpg)
