剑指offer专项突破版(68)—— 山峰数组的顶部_亚洲第一中锋_哈达迪的博客-爱代码爱编程
题目
思路
虽然整个数组并不是排序的,但分成前后两段后每段都分别排序,因此可以用二分法尝试
如果二分出某个中点mid:
- rr[mid] > arr[mid-1] && arr[mid] > arr[mid + 1] :mid比左右的元素都大,即找到山峰,直接返回
- arr[mid] < arr[mid+1] && arr[mid] > arr[mid-1] :mid比右边小,比左边大,说明山峰一定在右边,令
l = mid + 1
- arr[mid] > arr[mid + 1] && arr[mid] < arr[mid-1] :mid比右边小,比左边大,说明山峰一定在左边,令
r = mid - 1
代码
public int peakIndexInMountainArray(int[] arr) {
int l = 0;
int r = arr.length-1;
while(l <= r){
int mid = l + r >> 1;
if(mid == 0){
l = mid + 1;
continue;
}
if(mid == arr.length-1){
r = mid-1;
continue;
}
if (arr[mid] > arr[mid-1] && arr[mid] > arr[mid + 1]){
return mid;
}
if(arr[mid] < arr[mid+1] && arr[mid] > arr[mid-1]){
l = mid + 1;
}
if(arr[mid] > arr[mid + 1] && arr[mid] < arr[mid-1]){
r = mid - 1;
}
}
return l;
}