f*****e
发帖数: 2992 | 1 有一个数组，先严格递增，后严格递减，最大值位置不知道，给一个数，求这个数在数
组的位置(数组中有多少个数小于这个数)。可能是老题了。 |
h********6
发帖数: 285 | 2 可以先二分找到peak位置，O(logN)
然后在peak两边分别二分，O(logK) + O (log(N-K)) |
f*****e
发帖数: 2992 | 3 right,这个问题我没印象，今天career fair plantir一个哥们问的。侥幸答对了。
【在 h********6 的大作中提到】
: 可以先二分找到peak位置，O(logN)
: 然后在peak两边分别二分，O(logK) + O (log(N-K))
|
i*********7
发帖数: 348 | 4 先找到最大值，然后再分左右两边做binary search？
【在 f*****e 的大作中提到】
: 有一个数组，先严格递增，后严格递减，最大值位置不知道，给一个数，求这个数在数
: 组的位置(数组中有多少个数小于这个数)。可能是老题了。
|
a*******y
发帖数: 1040 | 5 Binary search in a rotated array, one of the problem in 150
【在 f*****e 的大作中提到】
: 有一个数组，先严格递增，后严格递减，最大值位置不知道，给一个数，求这个数在数
: 组的位置(数组中有多少个数小于这个数)。可能是老题了。
|
f*****e
发帖数: 2992 | 6 我的答案是二分查找，判断
1)a[n/2-1]>a[n/2]>a[n/2+1]，则最大值在左边，recurse on left
2)a[n/2-1]
3)a[n/2-1]a[n/2+1]，con~! you have found the largest number
【在 a*******y 的大作中提到】
: Binary search in a rotated array, one of the problem in 150
|
