给定一个双音数组和数组中的元素x，在2log（n）时间中找到x的索引 [英] Given a bitonic array and element x in the array, find the index of x in 2log(n) time

问题描述

首先，将这个问题的双音数组定义为这样，即对于长度为 N 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):

1. 取数组的中间


2. 将中间元素与其邻居之一进行比较，以查看最大值在右边还是在左边


3. 比较中间元素和期望值


4. 如果中间元素小于期望值并且最大值在左侧，则进行双音在左边的子数组中搜索（我们确定该值不在右边的子数组中）


5. 如果中间元素小于所需的值并且最大值在右边，则在右边的子数组上进行二元搜索


6. 如果中间元素大于所需的值，则在右边的子数组上进行降序二进制搜索，在左边的子数组上进行升序二进制搜索。 / li>
   

1. Take the middle of the array
2. Compare the middle element with one of its neighbor to see if the max is on the right or on the left
3. Compare the middle element with the desired value
4. If the middle element is smaller than the desired value AND the max is on the left side, then do bitonic search on the left subarray (we are sure that the value is not in the right subarray)
5. If the middle element is smaller than the desired value AND the max is on the right side, then do bitonic search on the right subarray
6. If the middle element is bigger than the desired value, then do descending binary search on the right subarray and ascending binary search on the left subarray.

在最后一种情况下，对可能具有双音调的子数组进行二进制搜索可能会令人惊讶，但实际上它是可行的，因为我们知道顺序不正确的元素都大于期望值。例如，对数组[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的索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！