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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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, 对左右两边， 每一边判断 １ 丢掉 ２ call binary search 3.
recursive this routine. |
n*******w
发帖数: 687 | 10 这个应该work。
可以更简化一下。只判断a[mid] 与 a[mid+1]的大小关系。
循环结束条件是left+1 == right。
【在 b******t 的大作中提到】
: 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 的大作中提到】
: 如果不考虑重复的话
: 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 的大作中提到】
: 这恐怕不够吧
|
c*********t
发帖数: 2921 | 15 good problem
point.
【在 x******9 的大作中提到】
: 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 的大作中提到】
: There are detailed analysis and solution in the blog:
: http://codercareer.blogspot.com/2011/11/no-22-turning-number-in
:
: point.
|
