问一道谷歌面经题

问一道google面经题，在glassdoor上面看到的：given a list of elements arranged in ascending and th

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

ted sorted array一样，写起来发现根本不是那么回事，求大神解答！！！

我有个想法。。先二分找到最大值的下标。这个和普通二分一样。就是判断mid的时候，要满足mid的value比两边大。。然后分成2个单调的数组，分别二分。

这不就是find peak element么，换了身衣服而已啊。

1. int findPeak(vector<int> nums) {
   
2.         int start = 0, end = nums.size()-1;
   
3.         while (start < end) {
   
4.                 int mid = start + (end-start)/2;
   
5.                 int midNext = mid+1;
   
6.                 if (nums[mid] > nums[midNext]) {
   
7.                         end = mid;
   
8.                 } else {
   
9.                         start = midNext;
   
10.                 }
    
11.         }
    
12.         return nums[start];
    
13. }

复制代码

测试过
1 2 3 4 5
5 4 3 2 1
1 4 5 3 2
都返回5

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

感觉没有O(n)的解法吧，因为找到中间点后没法判断是在它的左边还是右边

wenqiang88 发表于 2015-9-16 11:42
感觉没有O(n)的解法吧，因为找到中间点后没法判断是在它的左边还是右边

O(n)就是从头到尾扫一遍啊，你的意思是没有O(logn)的解法吗

kelvinzhong 发表于 2015-9-16 11:50
我觉得这题可以先去找peak， 然后对两边用binary search。

补充内容 (2015-9-16 11:51):

说的好有道理，这么说来应该算是O(logn)的复杂度

三次二分查找，还是logn的复杂度

这就不就是find peak element吗？leetcode有原题啊

或者说可以吧数组分成两部分，一个升序，一个降序，用一个变量记录peak element，然后两边分别二分