首先,针对这个问题定义了一个双元数组,使得对于长度为N的数组中的某个索引N,0 < K < N - 1和0到K是一个单调递增的整数序列,K到N-1是一个单调递减的整数序列。
例子:[1, 3, 4, 6, 9, 14, 11, 7, 2, -4, -9].它从1单调增加到14,然后从14下降到-9。
这个问题的前身是在3log(n)中解决它,这要容易得多。一个改变的二进制搜索找到最大的指数,然后两个二进制搜索分别对0到K和K+1到N-1。
我假设2log(n)中的解决方案需要您解决问题,而不需要找到最大值的索引。我考虑过重叠二进制搜索,但除此之外,我不知道如何向前迈进。
发布于 2014-06-07 15:39:11
其他答案(这 和 这)中提出的算法不幸不正确,它们不是O(logN) !
递归公式f(L) = f(L/2) + log(L/2) +c并不导致f(L) = O(log(N)),而是导致f(L) = O((log(N))^2)!
实际上,假设k= log(L),则log(2^(k-1)) + log(2^( k-2 )) +.+ log(2^1) = log(2)*(k-1 +k-2+.+ 1) = O(k^2)。因此,log(L/2) + log(L/4) +.+ log(2) =O(log(L)^2)。
解决time ~2 2log(N)问题的正确方法是按以下方式进行(假设数组先按升序,然后按降序排列):
在最后一种情况下,对一个可能是bitonic的子数组进行二进制搜索可能会令人惊讶,但它实际上是有效的,因为我们知道,没有良好顺序的元素都大于所期望的值。例如,对数组2、4、5、6、9、8、7中的值执行升序二进制搜索,因为7和8大于所需的值5。
这里有一个完全工作的实现(在C++中):时间~2logN中的双离子搜索
#include <iostream>
using namespace std;
const int N = 10;
void descending_binary_search(int (&array) [N], int left, int right, int value)
{
// cout << "descending_binary_search: " << left << " " << right << endl;
// empty interval
if (left == right) {
return;
}
// look at the middle of the interval
int mid = (right+left)/2;
if (array[mid] == value) {
cout << "value found" << endl;
return;
}
// interval is not splittable
if (left+1 == right) {
return;
}
if (value < array[mid]) {
descending_binary_search(array, mid+1, right, value);
}
else {
descending_binary_search(array, left, mid, value);
}
}
void ascending_binary_search(int (&array) [N], int left, int right, int value)
{
// cout << "ascending_binary_search: " << left << " " << right << endl;
// empty interval
if (left == right) {
return;
}
// look at the middle of the interval
int mid = (right+left)/2;
if (array[mid] == value) {
cout << "value found" << endl;
return;
}
// interval is not splittable
if (left+1 == right) {
return;
}
if (value > array[mid]) {
ascending_binary_search(array, mid+1, right, value);
}
else {
ascending_binary_search(array, left, mid, value);
}
}
void bitonic_search(int (&array) [N], int left, int right, int value)
{
// cout << "bitonic_search: " << left << " " << right << endl;
// empty interval
if (left == right) {
return;
}
int mid = (right+left)/2;
if (array[mid] == value) {
cout << "value found" << endl;
return;
}
// not splittable interval
if (left+1 == right) {
return;
}
if(array[mid] > array[mid-1]) {
if (value > array[mid]) {
return bitonic_search(array, mid+1, right, value);
}
else {
ascending_binary_search(array, left, mid, value);
descending_binary_search(array, mid+1, right, value);
}
}
else {
if (value > array[mid]) {
bitonic_search(array, left, mid, value);
}
else {
ascending_binary_search(array, left, mid, value);
descending_binary_search(array, mid+1, right, value);
}
}
}
int main()
{
int array[N] = {2, 3, 5, 7, 9, 11, 13, 4, 1, 0};
int value = 4;
int left = 0;
int right = N;
// print "value found" is the desired value is in the bitonic array
bitonic_search(array, left, right, value);
return 0;
}发布于 2013-10-15 04:13:50
该算法通过将双元搜索和二进制搜索结合起来递归地工作:
def bitonic_search (array, value, lo = 0, hi = array.length - 1)
if array[lo] == value then return lo
if array[hi] == value then return hi
mid = (hi + lo) / 2
if array[mid] == value then return mid
if (mid > 0 & array[mid-1] < array[mid])
| (mid < array.length-1 & array[mid+1] > array[mid]) then
# max is to the right of mid
bin = binary_search(array, value, low, mid-1)
if bin != -1 then return bin
return bitonic_search(array, value, mid+1, hi)
else # max is to the left of mid
bin = binary_search(array, value, mid+1, hi)
if bin != -1 then return bin
return bitonic_search(array, value, lo, mid-1) 因此,时间的递归公式是f(l) = f(l/2) + log(l/2) + c,其中log(l/2)来自二进制搜索,c是在函数体中进行比较的成本。
发布于 2014-03-16 20:49:54
所提供的答案的时间复杂度为(N/2)*logN。因为最坏的情况可能包括太多的子搜索,这是不必要的。修改是在搜索前将目标值与子序列的左、右元素进行比较。如果目标值不是在单调序列的两端之间,或者小于双元序列的两端,则后续搜索是多余的。这种修改导致了2lgN的复杂性。
https://stackoverflow.com/questions/19372930
复制相似问题