r******n
发帖数: 170 | 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;
}
没看懂解答为啥能保证是对的？ | c**********s
发帖数: 410 | 2
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******g
发帖数: 41 | 3 二分的变体呀
通过比较a[l]和a[m]判断数组的哪一半是单调的或者rotated | v*s
发帖数: 946 | 4 假设旋转前的数组是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*****n
发帖数: 5488 | 5 拿几个测试例子走走，根本这就不对。
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*s
发帖数: 946 | 6 较真的我喜欢。 我还真的放在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******n
发帖数: 170 | 7 多谢详细的解释，我没注意到一个简单的事实，随便砍一刀，肯定只有一边是乱序，一
边是递增
的。
然后就是判断到底是在递增的区域，还是在乱序的区域了。假如在递增的区域，马上就
变成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******n
发帖数: 170 | 8 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**********s
发帖数: 410 | 9
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******g
发帖数: 41 | 10 二分的变体呀
通过比较a[l]和a[m]判断数组的哪一半是单调的或者rotated | | | s*****n
发帖数: 5488 | 11 拿几个测试例子走走，根本这就不对。
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******n
发帖数: 170 | 12 多谢详细的解释，我没注意到一个简单的事实，随便砍一刀，肯定只有一边是乱序，一
边是递增
的。
然后就是判断到底是在递增的区域，还是在乱序的区域了。假如在递增的区域，马上就
变成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*******u
发帖数: 186 | 13 比较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*******u
发帖数: 186 | 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]) {
| z******t
发帖数: 59 | 15 这个博客里有这个问题详细的解答：
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****x
发帖数: 7404 | 16 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]) {
|
|
