P*****f
发帖数: 2272 | 1 在sorted array中找一个数，binary search。
有个题是sorted array right/left shift 了k位(k unkown)，问怎么查找。
这也是个老题了，我所知的solution是用modified binary search, 根据 left end,
right end 和middle point 的大小关系来判断下一次搜索的范围。不过今天突然想到
一个例子;
original array = { 1,2,3,3,3,3,3,3,3,3,3,3,,3,....3}. shift k位后成了
{3,3,3,3...3,1,2,3,3,3,3,3,3,3}.这个似乎二分查找无法搞定,只能线性搜索了吧。
讨论一下 | N********n
发帖数: 8363 | 2 int bsch (int[] a, int k, int val)
{ int l = 0, r = a.length - 1;
while (l < r)
{ int m = (l + r) / 2;
if (a[(m + k) % a.length] < val)
l = m + 1;
else if (a[(m + k) % a.length] > val)
r = m - 1;
else
return (m + k) % a.length; // found
}
return -1; // not found
}
【在 P*****f 的大作中提到】
: 在sorted array中找一个数，binary search。
: 有个题是sorted array right/left shift 了k位(k unkown)，问怎么查找。
: 这也是个老题了，我所知的solution是用modified binary search, 根据 left end,
: right end 和middle point 的大小关系来判断下一次搜索的范围。不过今天突然想到
: 一个例子;
: original array = { 1,2,3,3,3,3,3,3,3,3,3,3,,3,....3}. shift k位后成了
: {3,3,3,3...3,1,2,3,3,3,3,3,3,3}.这个似乎二分查找无法搞定,只能线性搜索了吧。
: 讨论一下
| P*****f
发帖数: 2272 | 3 k 是未知的
int bsch (int[] a, int k, int val)
{ int l = 0, r = a.length - 1;
while (l < r)
{ int m = (l + r) / 2;
if (a[(m + k) % a.length] < val)
l = m + 1;
else if (a[(m + k) % a.length] > val)
r = m - 1;
else
return (m + k) % a.length; // found
}
return -1; // not found
}
【在 N********n 的大作中提到】
: int bsch (int[] a, int k, int val)
: { int l = 0, r = a.length - 1;
: while (l < r)
: { int m = (l + r) / 2;
: if (a[(m + k) % a.length] < val)
: l = m + 1;
: else if (a[(m + k) % a.length] > val)
: r = m - 1;
: else
: return (m + k) % a.length; // found
| N********n
发帖数: 8363 | 4 int solveK (int[] a)
{
int l = 0, r = a.length - 1;
while (l < r) {
m = (l + r) / 2;
if (a[l] > a[m])
r = m;
else
l = m;
}
return l + 1;
}
bsch (a, solveK(a), val);
end,
想到
吧。
【在 P*****f 的大作中提到】
: k 是未知的
:
: int bsch (int[] a, int k, int val)
: { int l = 0, r = a.length - 1;
: while (l < r)
: { int m = (l + r) / 2;
: if (a[(m + k) % a.length] < val)
: l = m + 1;
: else if (a[(m + k) % a.length] > val)
: r = m - 1;
| s****u
发帖数: 118 | 5 这个我们讨论过啦，是要O(n)的
【在 P*****f 的大作中提到】
: 在sorted array中找一个数，binary search。
: 有个题是sorted array right/left shift 了k位(k unkown)，问怎么查找。
: 这也是个老题了，我所知的solution是用modified binary search, 根据 left end,
: right end 和middle point 的大小关系来判断下一次搜索的范围。不过今天突然想到
: 一个例子;
: original array = { 1,2,3,3,3,3,3,3,3,3,3,3,,3,....3}. shift k位后成了
: {3,3,3,3...3,1,2,3,3,3,3,3,3,3}.这个似乎二分查找无法搞定,只能线性搜索了吧。
: 讨论一下
| s****u
发帖数: 118 | 6 /cy 相等的时候不知道走那边的
【在 N********n 的大作中提到】
: int solveK (int[] a)
: {
: int l = 0, r = a.length - 1;
: while (l < r) {
: m = (l + r) / 2;
: if (a[l] > a[m])
: r = m;
: else
: l = m;
: }
| N********n
发帖数: 8363 | 7 I doubt so. It should still be log(N).
【在 s****u 的大作中提到】
: 这个我们讨论过啦，是要O(n)的
| N********n
发帖数: 8363 | 8 ???
【在 s****u 的大作中提到】
: /cy 相等的时候不知道走那边的
| s****u
发帖数: 118 | 9 找k的时候，就是找最小，但是不能你那样找的 :)
【在 N********n 的大作中提到】
: ???
| N********n
发帖数: 8363 | 10 oh i see.
【在 s****u 的大作中提到】
: 找k的时候，就是找最小，但是不能你那样找的 :)
| g****n
发帖数: 14 | 11 更准确地说，是O(log(N-M))+O(M)。
M是rotate前的数组中最长的不增子序列(即，该子序列中各项都相等)。
【在 s****u 的大作中提到】
: 这个我们讨论过啦，是要O(n)的
|
|
