题目:BM19 寻找峰值、力扣162. 寻找峰值
public class Solution {
/**
* 保持在上坡的一边一定可以找到峰值,上坡只有两种情况一直为上坡,或者变为下坡
这两种情况都符合有峰值条件,
因为nums[-1] = nums[n] = −∞, nums[i] != nums[i + 1],所以一定可以找到
* @param nums int整型一维数组
* @return int整型
*/
public int findPeakElement (int[] nums) {
if (nums.length == 1 || nums[0] > nums[1]) return 0;
int n = nums.length;
if (nums[n - 1] > nums[n - 2]) return n - 1;
int left = 0, right = nums.length - 1;
// [left, right] 左闭右闭,left == right 有意义
while (left <= right) {
int mid = left + (right - left >> 1);
// 右边为上坡 转到右半边
if (nums[mid] < nums[mid + 1]) left = mid + 1;
// 左边为上坡 转到左半边
else right = mid - 1; // 左闭右开
}
return left;
}
public int findPeakElement1 (int[] nums) {
int left = 0, right = nums.length - 1;
// [left, right) 左闭右开,left == right 无意义
while (left < right) {
int mid = left + (right - left >> 1);
// 右边为上坡 转到右半边
if (nums[mid] < nums[mid + 1]) left = mid + 1;
// 左边为上坡 转到左半边
else right = mid; // 左闭右开
}
return left;
}
}
总结:二分法什么时候用 left < right ,什么时候用 left <= right ?有什么区别。
对于二分查找来说,就是从数列的两端进行查找,更适合于对有序数列的查找操作,两端就是 left、right,其中查找途中还需要一个中间量mid表示中间值,正是这个中间值把当前数列一分为二,所以才叫二分查找。
一般情况来说,变量初始化如下:left = 0,right = nums.length - 1, mid = left + (right - left >> 1),位运算防止溢出。
情况一:使用 left < right,也就是左闭右开区间 [left, right),代码模板如下下:
// [left, right) 左闭右开,left == right 无意义,在循环中取不到值
while (left < right) {
int mid = left + (right - left >> 1);
if (nums[mid] < target) left = mid + 1;
// 左边为上坡 转到左半边
else if (nums[mid] < target) right = mid; // 左闭右开,防止mid娶不到值
else return mid;
}
情况二:使用 left > right,也就是左闭右闭区间 [left, right],代码模板如下下:
// [left, right] 左闭右闭,left == right 有意义,在循环中可以娶到
while (left <= right) {
int mid = left + (right - left >> 1);
if (nums[mid] < target) left = mid + 1;
// 左边为上坡 转到左半边
else if (nums[mid] < target) right = mid - 1; // 左闭右开,mid可以在循环中取到值
else return mid;
}
标签:right,nums,int,mid,通俗易懂,二分法,讲解,左闭,left
From: https://www.cnblogs.com/malongfeistudy/p/16784786.html