给定一个双调数组和数组中的元素 x，在 2log(n) 时间内找到 x 的索引

首先，这个问题的双调数组被定义为对于某些索引K在长度数组中N where 0 < K < N - 10到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)要求您在不找到最大值索引的情况下解决问题。我考虑过重叠二进制搜索，但除此之外，我不确定如何继续前进。

其他答案中提出的算法（this https://stackoverflow.com/a/21697488/509868 and this https://stackoverflow.com/a/19373178/509868) 不幸的是不正确，它们不是 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;
}