首先,将这个问题的双音数组定义为这样,即对于长度为 N $ c的数组中的某些索引 K $ c>其中 0< K < N-1 和0到K是整数的单调递增序列,而K到N-1是整数的单调递减序列。
First, a bitonic array for this question is defined as one such that for some index K in an array of length N where 0 < K < N - 1 and 0 to K is a monotonically increasing sequence of integers, and K to N - 1 is a monotonically decreasing sequence of integers.
示例: [1、3、4、6、9、14、11、7、2,-4,-9] 。它从1到14单调增加,然后从14减小到-9。
Example: [1, 3, 4, 6, 9, 14, 11, 7, 2, -4, -9]. It monotonically increases from 1 to 14, then decreases from 14 to -9.
这个问题的前身是在 3log(n)中解决它,这要容易得多。一种更改后的二进制搜索以找到最大值的索引,然后分别进行两次二进制搜索,分别从0到K和K +1到N-1。
The precursor to this question is to solve it in 3log(n), which is much easier. One altered binary search to find the index of the max, then two binary searchs for 0 to K and K + 1 to N - 1 respectively.
我假定 2log(n)要求您解决问题而没有找到最大值的索引。我曾考虑过将二进制搜索重叠,但除此之外,我不确定如何继续前进。
I presume the solution in 2log(n) requires you solve the problem without finding the index of the max. I've thought about overlapping the binary searches, but beyond that, I'm not sure how to move forward.
推荐答案其他答案中提出的算法(此和此)很不正确,它们不是O(logN)!
The algorithms presented in other answers (this and this) are unfortunately incorrect, they are not O(logN) !
递归公式f(L)= f(L / 2)+ log(L / 2)+ c不会导致f(L) = O(log(N))但导致f(L)= O((log(N))^ 2)!
The recursive formula f(L) = f(L/2) + log(L/2) + c doesn't lead to f(L) = O(log(N)) but leads to 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))。
Indeed, assume k = log(L), then log(2^(k-1)) + log(2^(k-2)) + ... + log(2^1) = log(2)*(k-1 + k-2 + ... + 1) = O(k^2). Hence, log(L/2) + log(L/4) + ... + log(2) = O((log(L)^2)).
及时解决问题的正确方法〜2log(N)如下进行操作(假设数组首先以升序排列,然后以降序排列):
The right way to solve the problem in time ~ 2log(N) is to proceed as follows (assuming the array is first in ascending order and then in descending order):
在最后一种情况下,对可能具有双音调的子数组进行二进制搜索可能会令人惊讶,但实际上它是可行的,因为我们知道顺序不正确的元素都大于期望值。例如,对数组[2、4、5、6、9、8、7]中的值5进行升序二进制搜索将起作用,因为7和8大于所需值5。
In the last case, it might be surprising to do a binary search on a subarray that may be bitonic but it actually works because we know that the elements that are not in the good order are all bigger than the desired value. For instance, doing an ascending binary search for the value 5 in the array [2, 4, 5, 6, 9, 8, 7] will work because 7 and 8 are bigger than the desired value 5.
在时间〜2logN 中,这是双向搜索的完全有效的实现(在C ++中):
Here is a fully working implementation (in C++) of the bitonic search in time ~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; }更多推荐
给定一个双音数组和数组中的元素x,在2log(n)时间中找到x的索引
发布评论