C***y
发帖数: 2546 | |
i*********7
发帖数: 348 | |
C***y
发帖数: 2546 | 3 二分以后怎么排除一半呢？
【在 i*********7 的大作中提到】
: 二分查找
|
w****x
发帖数: 2483 | 4
二分原理是基于位置而不是数字, 啥时候觉得该向左找右边一半就排除了
【在 C***y 的大作中提到】
: 二分以后怎么排除一半呢？
|
C***y
发帖数: 2546 | 5 能稍微详细讲讲不？
谢谢
【在 w****x 的大作中提到】
:
: 二分原理是基于位置而不是数字, 啥时候觉得该向左找右边一半就排除了
|
a*******y
发帖数: 1040 | 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*******1
发帖数: 2454 | 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*****a
发帖数: 14598 | 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*******1
发帖数: 2454 | 9 谢谢，我傻了。
【在 l*****a 的大作中提到】
: obviously, it just doesn't support dup
: once there is dup, u need a full scan
|
C***y
发帖数: 2546 | 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 (L
if(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**u
发帖数: 504 | 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(l
m=(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*******y
发帖数: 1040 | 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***y
发帖数: 2546 | 13 嗯，你的应该是对的
我看错了
【在 a*******y 的大作中提到】
: 怎么不对了，这个return是L-1，not L
|
