二分法 — 找峰值问题
给你一个整数数组 nums,已知任何两个相邻的值都不相等,找到峰值元素并返回其索引,数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可,现时间复杂度为 O(log n) 的算法来解决此问题
注意:峰值不是最大值,峰值元素是指其值严格大于左右相邻值的元素
思路
整数数组 nums 任何两个相邻的值都不相等,说明相邻两个数之间一定能区分出大小
- Step1:先看下标为 0 和 length-1 位置的元素(即 L 和 R )是不是峰值
- Step2:若下标为 0 和 length-1 位置的元素不是峰值,那就看中间位置(即M)的元素是不是峰值
- Step3:若中间位置的元素是不是峰值,若果是右边元素大于中间元素,那么右边区间一定有峰值,反之就从左边找,如果两边元素都大于中间元素,那么任选一边即可,因为只要求返回一个峰值
Java实现
public static int findPeakElement(int[] arr) {
int n = arr.length;
//先决条件:若数组长度为1,那么唯一存在的元素就是该数组的峰值点,返回下标0
if (arr.length == 1) {
return 0;
}
//判断下标为 0 的元素是否为峰值,即与下标为 1 的元素比较大小
if (arr[0] > arr[1]) {
return 0;
}
//判断下标为 n-1 的元素是否为峰值,即与下标为 n-2 的元素比较大小
if (arr[n - 1] > arr[n - 2]) {
return n - 1;
}
int l = 1, r = n - 2, m = 0, index = -1;
while (l <= r) {
m = (l + r) / 2;
//判断下标为 m 的元素是否为峰值,即分别与下标为 m-1 和 m-2 的元素比较大小
//若 arr[m-1] > arr[m] 说明左边一定存在峰值
if (arr[m - 1] > arr[m]) {
r = m - 1;
}
//若 arr[m+1] > arr[m] 说明左边一定存在峰值
else if (arr[m] < arr[m + 1]) {
l = m + 1;
}
else {
index = m;
break;
}
}
return index;
}
C语言实现
和 Java 没什么区别,就是函数的参数加了一个数组长度 n ,因为C语言传递的是地址,不能在函数中直接计算数组长度
int findPeakElement(int arr[], int n) {
if (n == 1) {
return 0;
}
if (arr[0] > arr[1]) {
return 0;
}
if (arr[n - 1] > arr[n - 2]) {
return n - 1;
}
int l = 1, r = n - 2, m = 0, index = -1;
while (l <= r) {
m = (l + r) / 2;
if (arr[m - 1] > arr[m]) {
r = m - 1;
}
else if (arr[m] < arr[m + 1]) {
l = m + 1;
}
else {
index = m;
break;
}
}
return index;
}