关于在rotated sorted array中查找的问题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Programming - 葵花宝典

关于在rotated sorted array中查找的问题

关于在rotated sorted array中查找的问题# Programming - 葵花宝典

P*f2007-09-21 07:09

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*n2007-09-21 07:09

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*f2007-09-21 07:09

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*n2007-09-21 07:09

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;