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