x******9 发帖数: 473 | 1 An array, increasing order and the beginning and then decrease from 1 point.
How to find the point in log(N)? I had no idea in the interview.
最近脑子短路,麻烦大家给个思路。
test case:
1 2 3 4 5 10 9 8 7 6
1 2 3 4 5 4 3 2 |
q****x 发帖数: 7404 | 2 unimodal search, just like binary search.
point.
【在 x******9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : An array, increasing order and the beginning and then decrease from 1 point. : How to find the point in log(N)? I had no idea in the interview. : 最近脑子短路,麻烦大家给个思路。 : test case: : 1 2 3 4 5 10 9 8 7 6 : 1 2 3 4 5 4 3 2
|
b******t 发帖数: 965 | 3 recursion
if a[mid-1]< a[mid]>a[mid+1]
then return mid
else if a[mid-1]
right part
else
left part
point.
【在 x******9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : An array, increasing order and the beginning and then decrease from 1 point. : How to find the point in log(N)? I had no idea in the interview. : 最近脑子短路,麻烦大家给个思路。 : test case: : 1 2 3 4 5 10 9 8 7 6 : 1 2 3 4 5 4 3 2
|
H*M 发帖数: 1268 | 4 binary search? 如果 mid 的左边和右边分别是 上升 上升 则去掉左边, 下将下降
去掉右边, 下降下降则是解 |
f*******t 发帖数: 7549 | 5 这就是search rotated array的变种 |
A**u 发帖数: 2458 | 6 你这个好写不
【在 b******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : recursion : if a[mid-1]< a[mid]>a[mid+1] : then return mid : else if a[mid-1]: right part : else : left part : : point.
|
s******n 发帖数: 226 | 7 这是最基本的离散优化问题,binary search本质上是求导数 |
z******t 发帖数: 59 | 8 There are detailed analysis and solution in the blog:
http://codercareer.blogspot.com/2011/11/no-22-turning-number-in
point.
【在 x******9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : An array, increasing order and the beginning and then decrease from 1 point. : How to find the point in log(N)? I had no idea in the interview. : 最近脑子短路,麻烦大家给个思路。 : test case: : 1 2 3 4 5 10 9 8 7 6 : 1 2 3 4 5 4 3 2
|
s******e 发帖数: 114 | 9 it will return 0/1/2 results
In binary search, 对左右两边, 每一边判断 1 丢掉 2 call binary search 3.
recursive this routine. |
n*******w 发帖数: 687 | 10 这个应该work。
可以更简化一下。只判断a[mid] 与 a[mid+1]的大小关系。
循环结束条件是left+1 == right。
【在 b******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : recursion : if a[mid-1]< a[mid]>a[mid+1] : then return mid : else if a[mid-1]: right part : else : left part : : point.
|
|
|
a**********2 发帖数: 340 | 11 这题假定没有重复的point对吧?要不worst case是O(n) |
a**********2 发帖数: 340 | 12 如果不考虑重复的话
int findTop(int* arr, int n)
{
int low = 0;
int high = n-1;
while( low < high)
{
int mid = low + (high-low)/2;
if( arr[mid] > arr[mid+1])
high = mid;
else
low = mid+1;
}
return high;
} |
A**u 发帖数: 2458 | 13 这恐怕不够吧
【在 a**********2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果不考虑重复的话 : int findTop(int* arr, int n) : { : int low = 0; : int high = n-1; : while( low < high) : { : int mid = low + (high-low)/2; : if( arr[mid] > arr[mid+1]) : high = mid;
|
a**********2 发帖数: 340 | 14 反例?
【在 A**u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这恐怕不够吧
|
c*********t 发帖数: 2921 | 15 good problem
point.
【在 x******9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : An array, increasing order and the beginning and then decrease from 1 point. : How to find the point in log(N)? I had no idea in the interview. : 最近脑子短路,麻烦大家给个思路。 : test case: : 1 2 3 4 5 10 9 8 7 6 : 1 2 3 4 5 4 3 2
|
x******9 发帖数: 473 | 16 谢谢,这个清楚,之前光想着两边了,原来是看中间那个元素...nc了...
【在 z******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : There are detailed analysis and solution in the blog: : http://codercareer.blogspot.com/2011/11/no-22-turning-number-in : : point.
|