给定数组中的bitonic数组和元素x,在2log(n)时间内找到x的索引

Question

首先,针对该问题的比特阵列被定义为对于K长度数组中的某个索引,N其中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),这更容易.一个改变的二进制搜索找到max的索引,然后两个二进制搜索分别为0到K和K + 1到N-1.

我认为解决方案2log(n)要求你在没有找到最大索引的情况下解决问题.我考虑过重叠二进制搜索,但除此之外,我不确定如何继续前进.

Answer 1

不幸的是,其他答案(本和本)中提出的算法不正确,它们不是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. 如果中间元素小于期望值并且最大值在左侧,则在左子阵列上进行bitonic搜索(我们确定该值不在右侧子阵列中)
5. 如果中间元素小于期望值并且最大值在右侧,则在右侧子阵列上进行bitonic搜索
6. 如果中间元素大于期望值,则在右子阵列上进行二进制搜索,在左子阵列上进行二进制搜索.

在最后一种情况下,对子阵列进行二元搜索可能会很奇怪,这可能是有点的,但它实际上是有效的,因为我们知道不正常的元素都大于所需的值.例如,对数组[2,4,5,6,9,8,7]中的值5进行升序二分搜索将起作用,因为7和8大于期望值5.

这是一个完全工作的实现(在C++中)的bitonic搜索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;
}