p***o
发帖数: 44 | 1 不记得在哪里看到这道编程题：
一个排好序的数组，本来是可以用二分查找O(log n)找到一个数。
可是现在这个数组被切成了两半，然后前后换了一下位置。
比如：2 3 5 8 10 15 30
变成：15 30 2 3 5 8 10
切断的位置未知。在这种情况下，请找出一种办法用最快的速度找到一个数。 |
g*****g
发帖数: 34805 | 2 It's O(log n) to find the break point, so it's still
O(log n)
【在 p***o 的大作中提到】
: 不记得在哪里看到这道编程题：
: 一个排好序的数组，本来是可以用二分查找O(log n)找到一个数。
: 可是现在这个数组被切成了两半，然后前后换了一下位置。
: 比如：2 3 5 8 10 15 30
: 变成：15 30 2 3 5 8 10
: 切断的位置未知。在这种情况下，请找出一种办法用最快的速度找到一个数。
|
p***o
发帖数: 44 | 3 想了一下，不明白为啥O(log n)能找到断点
【在 g*****g 的大作中提到】
: It's O(log n) to find the break point, so it's still
: O(log n)
|
p***o
发帖数: 44 | 4 哦。你假设调换前的数组是已知的？
【在 p***o 的大作中提到】
: 想了一下，不明白为啥O(log n)能找到断点
|
g*****g
发帖数: 34805 | 5 check first and last and middle one, if they are in order,
the whole array is in order. Otherwise, check left half,
or check right half in binary fashion, I am too lazy to
think of exact algorithm, but something like that should work.
【在 p***o 的大作中提到】
: 想了一下，不明白为啥O(log n)能找到断点
|
c*****t
发帖数: 1879 | 6 Small caveat, there should be no duplicates in the array. Otherwise,
it would take O (n) with an extreme case of
original:
[ 0 1 1 ... ]
rotated:
[ 1 1 ... 0 1 ... ]
【在 g*****g 的大作中提到】
: It's O(log n) to find the break point, so it's still
: O(log n)
|
p***o
发帖数: 44 | 7 强！这些题很常见吗？呵呵
【在 c*****t 的大作中提到】
: Small caveat, there should be no duplicates in the array. Otherwise,
: it would take O (n) with an extreme case of
: original:
: [ 0 1 1 ... ]
: rotated:
: [ 1 1 ... 0 1 ... ]
|
