给定一个双音数组和数组中的元素x，在2log（n）时间中找到x的索引

给定一个双音数组和数组中的元素x，在2log（n）时间中找到x的索引

不幸的是，其他答案中提出的算法是错误的，它们不是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））。

在〜2log（N）的时间范围内解决问题的正确方法是按以下步骤进行 *** 作（假设数组首先以升序排列，然后以降序排列）：

1. 取数组的中间
2. 将中间元素与其相邻元素进行比较，以查看最大值在右边还是在左边
3. 比较中间元素与期望值
4. 如果中间元素小于所需的值，并且最大值在左侧，则在左侧子数组上进行双音位搜索（我们确保该值不在右侧子数组中）
5. 如果中间元素小于所需值并且最大值在右侧，则在右侧子数组上进行双音位搜索
6. 如果中间元素大于所需的值，则在右子数组上进行降序二进制搜索，并在左子数组上进行升序二进制搜索。

在最后一种情况下，对可能是双音位的子数组进行二进制搜索可能会令人惊讶，但它实际上可以工作，因为我们知道排列不佳的元素都大于所需值。例如，对数组[2、4、5、6、9、8、7]中的值5进行升序二进制搜索将起作用，因为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;}