find max in shifted sorted array - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

find max in shifted sorted array

find max in shifted sorted array# JobHunting - 待字闺中

C*y2012-09-08 07:09

1 楼

来自http://www.mitbbs.com/article_t1/JobHunting/32202217_0_1.html
请问这题怎么解？
谢谢

i*72012-09-08 07:09

2 楼

二分查找

C*y2012-09-08 07:09

3 楼

二分以后怎么排除一半呢？

【在 i*********7 的大作中提到】

: 二分查找

w*x2012-09-08 07:09

4 楼

二分原理是基于位置而不是数字, 啥时候觉得该向左找右边一半就排除了

【在 C***y 的大作中提到】

: 二分以后怎么排除一半呢？

C*y2012-09-08 07:09

5 楼

能稍微详细讲讲不？
谢谢

【在 w****x 的大作中提到】

:
: 二分原理是基于位置而不是数字, 啥时候觉得该向左找右边一半就排除了

a*y2012-09-08 07:09

6 楼

int FindSortedArrayMax(int A[], int N) {
int L = 0;
int R = N - 1;
while (A[L] > A[R]) {
int M = L + (R - L) / 2;
if (A[M] > A[R])
L = M + 1;
else
R = M;
}
return L == 0 ？ A[N-1] : A[L-1];
}

B*12012-09-08 07:09

7 楼

Your code seems not right for this case:
3 5 1 3 3

【在 a*******y 的大作中提到】

: int FindSortedArrayMax(int A[], int N) {
: int L = 0;
: int R = N - 1;
: while (A[L] > A[R]) {
: int M = L + (R - L) / 2;
: if (A[M] > A[R])
: L = M + 1;
: else
: R = M;
: }

l*a2012-09-08 07:09

8 楼

obviously, it just doesn't support dup
once there is dup, u need a full scan

【在 B*******1 的大作中提到】

: Your code seems not right for this case:
: 3 5 1 3 3

B*12012-09-08 07:09

9 楼

谢谢，我傻了。

【在 l*****a 的大作中提到】

: obviously, it just doesn't support dup
: once there is dup, u need a full scan

C*y2012-09-08 07:09

10 楼

谢谢！
但是感觉不太对，比如说3，4，5,1，2
M = 2, A[2] > A[4] ==> L = 3
L实际上应该等于2
我稍微修改了一下你的程序，如下：
int FindSortedArrayMax(int A[], int N) {
int L = 0;
int R = N - 1;
while (Lif(A[L] < A[R]) return R;
int M = L + (R - L) / 2;
if (A[M] > A[R])
{
if(L == M) break;
L = M;
}
else
R = M -1;
}
return L;
}

【在 a*******y 的大作中提到】

: int FindSortedArrayMax(int A[], int N) {
: int L = 0;
: int R = N - 1;
: while (A[L] > A[R]) {
: int M = L + (R - L) / 2;
: if (A[M] > A[R])
: L = M + 1;
: else
: R = M;
: }

g*u2012-09-08 07:09

11 楼

看我的这个行不行？
#include
#include
using namespace std;
int maxShiftedSortArray(vector& array){
int n=array.size();
if(n==1)
return array[0];
int l=0;
int r=n-1;
int m;
while(lm=(r+l)/2;
if(array[m]>=array[l]){
l=m;
}else{
r=m-1;
}
}
return max(array[l],array[r]);
}

【在 C***y 的大作中提到】

: 来自http://www.mitbbs.com/article_t1/JobHunting/32202217_0_1.html
: 请问这题怎么解？
: 谢谢

a*y2012-09-08 07:09

12 楼

怎么不对了，这个return是L-1，not L

【在 C***y 的大作中提到】

: 谢谢！
: 但是感觉不太对，比如说3，4，5,1，2
: M = 2, A[2] > A[4] ==> L = 3
: L实际上应该等于2
: 我稍微修改了一下你的程序，如下：
: int FindSortedArrayMax(int A[], int N) {
: int L = 0;
: int R = N - 1;
: while (L: if(A[L] < A[R]) return R;

C*y2012-09-08 07:09

13 楼

嗯，你的应该是对的
我看错了

【在 a*******y 的大作中提到】

: 怎么不对了，这个return是L-1，not L