收集了一下PPMMeng的经典语录 (转载) - 未名空间MITBBS历史存档

收集了一下PPMMeng的经典语录 (转载)# Joke - 肚皮舞运动

r*n2011-02-27 08:02

1 楼

Given a sorted array of n integers that has been rotated an unknown number
of times, give an O(log n) algorithm that finds an element in the array. You
may assume that the array was originally sorted in increasing order。
int search(int a[], int l, int u, int x) {
while (l <= u) {
int m = (l + u) / 2;
if (x == a[m]) {
return m;
} else if (a[l] <= a[m]) {
if (x > a[m]) {
l=m+1;
} else if (x >=a [l]) {
u = m-1;
} else {
l = m+1;
}
}
else if (x < a[m]) u = m-1;
else if (x <= a[u]) l = m+1;
else u = m-1;
}
return -1;
}
没看懂解答为啥能保证是对的？

s*02011-02-27 08:02

2 楼

【以下文字转载自 Piebridge 讨论区】
发信人: haiduc (鸳鸯茶), 信区: Piebridge
标题: 收集了一下PPMMeng的经典语录
发信站: BBS 未名空间站 (Sun Feb 27 20:34:33 2011, 美东)
1，妈个b的，要是这种婆婆来我家，我就用钥匙把房门从里面锁上，it敲死了我也不开！
2，女生很精贵的身体在婆婆眼里就和母猪一样。
3，敢用手戳人家身体就别怕挨巴掌。
4，又没技术又没情趣，你以为xxoo是上厕所啊？
5，所谓相爱就是男人挑逗起女人的sex欲望让她们失去理智就算成功。
6，不能给男人全面开发自己的机会，只能浅尝辄止，以免被动。
余下请补充.

c*s2011-02-27 08:02

3 楼

You

【在 r******n 的大作中提到】

: Given a sorted array of n integers that has been rotated an unknown number
: of times, give an O(log n) algorithm that finds an element in the array. You
: may assume that the array was originally sorted in increasing order。
: int search(int a[], int l, int u, int x) {
: while (l <= u) {
: int m = (l + u) / 2;
: if (x == a[m]) {
: return m;
: } else if (a[l] <= a[m]) {
: if (x > a[m]) {

x*g2011-02-27 08:02

4 楼

二分的变体呀
通过比较a[l]和a[m]判断数组的哪一半是单调的或者rotated

v*s2011-02-27 08:02

5 楼

假设旋转前的数组是1到11.
旋转后有两种可能性。
case 1)
8,9,10,11, 1,2,3,4,5,6,7
case 2）
4,5,6,7,8,9,10,11, 1,2,3
还是中间切一刀。先比中间那个数，如果lucky，那就找到了。
否则决定要选哪边继续比较。
如果 a[l] < a[m] 说明前半截是顺序的，例如上面的case 2）
>>>> 如果 a[l] <= x < a[m] 那就选前半截，否则选后半截。
否则（说明后半截是顺序的，参考case 1））
>>>> 如果 a[m] < x <= a[u] 那就选前后截，否则选前半截。
以此类推。
主要考点：二分法，一刀分成两截，只和顺序的那半截进行比较。如果确定不在那里
面，就在乱序的那半截。

You

【在 r******n 的大作中提到】

: Given a sorted array of n integers that has been rotated an unknown number
: of times, give an O(log n) algorithm that finds an element in the array. You
: may assume that the array was originally sorted in increasing order。
: int search(int a[], int l, int u, int x) {
: while (l <= u) {
: int m = (l + u) / 2;
: if (x == a[m]) {
: return m;
: } else if (a[l] <= a[m]) {
: if (x > a[m]) {

s*n2011-02-27 08:02

6 楼

拿几个测试例子走走，根本这就不对。
6712345

You

【在 r******n 的大作中提到】

: Given a sorted array of n integers that has been rotated an unknown number
: of times, give an O(log n) algorithm that finds an element in the array. You
: may assume that the array was originally sorted in increasing order。
: int search(int a[], int l, int u, int x) {
: while (l <= u) {
: int m = (l + u) / 2;
: if (x == a[m]) {
: return m;
: } else if (a[l] <= a[m]) {
: if (x > a[m]) {

v*s2011-02-27 08:02

7 楼

较真的我喜欢。我还真的放在gcc里跑了一圈。是对的啊。
int aa[] = { 6,7,1,2,3,4,5};
int main(void)
{
int i;
for(i=0;i<=10;++i)
{
printf("search for %d, location: %d\n", i ,search(aa, 0, 6, i));
}
}
$ ./a.out
search for 0, location: -1
search for 1, location: 2
search for 2, location: 3
search for 3, location: 4
search for 4, location: 5
search for 5, location: 6
search for 6, location: 0
search for 7, location: 1
search for 8, location: -1
search for 9, location: -1
search for 10, location: -1

【在 s*****n 的大作中提到】

: 拿几个测试例子走走，根本这就不对。
: 6712345
:
: You

r*n2011-02-27 08:02

8 楼

多谢详细的解释，我没注意到一个简单的事实，随便砍一刀，肯定只有一边是乱序，一
边是递增
的。
然后就是判断到底是在递增的区域，还是在乱序的区域了。假如在递增的区域，马上就
变成binary
search；不在递增区域，就划分到乱序区域继续砍。
下标应该也可以改成:
int search(int a[], int l, int u, int x) {
while (l <= u)
{
int m = (l + u) / 2;
if (x == a[m])
{
return m;
}
else if (a[l] <= a[m])
{
if (x < a[l])
{
l=m+1;
}
else if (x{
u = m-1;
}
else
{
l = m+1;
}
}
else if (x > a[u])
u = m-1;
else if (x >a[m])
l = m+1;
else
u = m-1;
}

i));

【在 v*s 的大作中提到】

: 较真的我喜欢。我还真的放在gcc里跑了一圈。是对的啊。
: int aa[] = { 6,7,1,2,3,4,5};
: int main(void)
: {
: int i;
: for(i=0;i<=10;++i)
: {
: printf("search for %d, location: %d\n", i ,search(aa, 0, 6, i));
: }
: }

r*n2011-02-27 08:02

9 楼

Given a sorted array of n integers that has been rotated an unknown number
of times, give an O(log n) algorithm that finds an element in the array. You
may assume that the array was originally sorted in increasing order。
int search(int a[], int l, int u, int x) {
while (l <= u) {
int m = (l + u) / 2;
if (x == a[m]) {
return m;
} else if (a[l] <= a[m]) {
if (x > a[m]) {
l=m+1;
} else if (x >=a [l]) {
u = m-1;
} else {
l = m+1;
}
}
else if (x < a[m]) u = m-1;
else if (x <= a[u]) l = m+1;
else u = m-1;
}
return -1;
}
没看懂解答为啥能保证是对的？

c*s2011-02-27 08:02

10 楼

You

【在 r******n 的大作中提到】

: Given a sorted array of n integers that has been rotated an unknown number
: of times, give an O(log n) algorithm that finds an element in the array. You
: may assume that the array was originally sorted in increasing order。
: int search(int a[], int l, int u, int x) {
: while (l <= u) {
: int m = (l + u) / 2;
: if (x == a[m]) {
: return m;
: } else if (a[l] <= a[m]) {
: if (x > a[m]) {

x*g2011-02-27 08:02

11 楼

二分的变体呀
通过比较a[l]和a[m]判断数组的哪一半是单调的或者rotated

s*n2011-02-27 08:02

12 楼

拿几个测试例子走走，根本这就不对。
6712345

You

【在 r******n 的大作中提到】

: Given a sorted array of n integers that has been rotated an unknown number
: of times, give an O(log n) algorithm that finds an element in the array. You
: may assume that the array was originally sorted in increasing order。
: int search(int a[], int l, int u, int x) {
: while (l <= u) {
: int m = (l + u) / 2;
: if (x == a[m]) {
: return m;
: } else if (a[l] <= a[m]) {
: if (x > a[m]) {

r*n2011-02-27 08:02

13 楼

多谢详细的解释，我没注意到一个简单的事实，随便砍一刀，肯定只有一边是乱序，一
边是递增
的。
然后就是判断到底是在递增的区域，还是在乱序的区域了。假如在递增的区域，马上就
变成binary
search；不在递增区域，就划分到乱序区域继续砍。
下标应该也可以改成:
int search(int a[], int l, int u, int x) {
while (l <= u)
{
int m = (l + u) / 2;
if (x == a[m])
{
return m;
}
else if (a[l] <= a[m])
{
if (x < a[l])
{
l=m+1;
}
else if (x{
u = m-1;
}
else
{
l = m+1;
}
}
else if (x > a[u])
u = m-1;
else if (x >a[m])
l = m+1;
else
u = m-1;
}

i));

【在 v*s 的大作中提到】

: 较真的我喜欢。我还真的放在gcc里跑了一圈。是对的啊。
: int aa[] = { 6,7,1,2,3,4,5};
: int main(void)
: {
: int i;
: for(i=0;i<=10;++i)
: {
: printf("search for %d, location: %d\n", i ,search(aa, 0, 6, i));
: }
: }

d*u2011-02-27 08:02

14 楼

比较element和中间元素，如果相同返回。
否则递归找该element在左边和右边：
左边: rotated sorted or sorted.
ratated sorted: recursive.
sorted: binary search.
similarly for the right side.

You

【在 r******n 的大作中提到】

: Given a sorted array of n integers that has been rotated an unknown number
: of times, give an O(log n) algorithm that finds an element in the array. You
: may assume that the array was originally sorted in increasing order。
: int search(int a[], int l, int u, int x) {
: while (l <= u) {
: int m = (l + u) / 2;
: if (x == a[m]) {
: return m;
: } else if (a[l] <= a[m]) {
: if (x > a[m]) {

d*u2011-02-27 08:02

15 楼

比较element和中间元素，如果相同返回。
否则递归找该element在左边和右边：
左边: rotated sorted or sorted.
ratated sorted: recursive.
sorted: binary search.
similarly for the right side.

You

【在 r******n 的大作中提到】

: Given a sorted array of n integers that has been rotated an unknown number
: of times, give an O(log n) algorithm that finds an element in the array. You
: may assume that the array was originally sorted in increasing order。
: int search(int a[], int l, int u, int x) {
: while (l <= u) {
: int m = (l + u) / 2;
: if (x == a[m]) {
: return m;
: } else if (a[l] <= a[m]) {
: if (x > a[m]) {

z*t2011-02-27 08:02

16 楼

这个博客里有这个问题详细的解答：
http://zhedahht.blog.163.com/blog/static/2541117420095276512054

You

【在 r******n 的大作中提到】

: Given a sorted array of n integers that has been rotated an unknown number
: of times, give an O(log n) algorithm that finds an element in the array. You
: may assume that the array was originally sorted in increasing order。
: int search(int a[], int l, int u, int x) {
: while (l <= u) {
: int m = (l + u) / 2;
: if (x == a[m]) {
: return m;
: } else if (a[l] <= a[m]) {
: if (x > a[m]) {

q*x2011-02-27 08:02

17 楼

why you need x?

You

【在 r******n 的大作中提到】

: Given a sorted array of n integers that has been rotated an unknown number
: of times, give an O(log n) algorithm that finds an element in the array. You
: may assume that the array was originally sorted in increasing order。
: int search(int a[], int l, int u, int x) {
: while (l <= u) {
: int m = (l + u) / 2;
: if (x == a[m]) {
: return m;
: } else if (a[l] <= a[m]) {
: if (x > a[m]) {