首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >给定一个双离子阵列和数组中的元素x,在2log(n)时间内找到x的索引。

问给定一个双离子阵列和数组中的元素x,在2log(n)时间内找到x的索引。
EN

Stack Overflow用户
提问于 2013-10-15 03:42:11
回答 8查看 20K关注 0票数 26

首先,针对这个问题定义了一个双元数组,使得对于长度为N的数组中的某个索引N,0 < K < N - 1和0到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)中的解决方案需要您解决问题,而不需要找到最大值的索引。我考虑过重叠二进制搜索,但除此之外,我不知道如何向前迈进。

EN

回答 8

Stack Overflow用户

回答已采纳

发布于 2014-06-07 15:39:11

其他答案(这 和 这)中提出的算法不幸不正确,它们不是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)。

解决time ~2 2log(N)问题的正确方法是按以下方式进行(假设数组先按升序,然后按降序排列):

  1. 取数组的中间
  2. 将中间元素与它的一个相邻元素进行比较,看看最大值是在右边还是在左边。
  3. 将中间元素与所需的值进行比较
  4. 如果中间元素小于所需值,最大值位于左侧,则对左侧子数组执行双声速搜索(我们确定该值不在右侧子数组中)。
  5. 如果中间元素小于所需值,且最大值位于右侧,则对右子数组执行双声速搜索。
  6. 如果中间元素大于所需值,则对右侧子数组执行降序二进制搜索,在左侧子数组上执行升序二进制搜索。

在最后一种情况下,对一个可能是bitonic的子数组进行二进制搜索可能会令人惊讶,但它实际上是有效的,因为我们知道,没有良好顺序的元素都大于所期望的值。例如,对数组2、4、5、6、9、8、7中的值执行升序二进制搜索,因为7和8大于所需的值5。

这里有一个完全工作的实现(在C++中):时间~2logN中的双离子搜索

代码语言:javascript
复制
#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;
}
票数 54
EN

Stack Overflow用户

发布于 2013-10-15 04:13:50

该算法通过将双元搜索和二进制搜索结合起来递归地工作:

代码语言:javascript
复制
def bitonic_search (array, value, lo = 0, hi = array.length - 1)
  if array[lo] == value then return lo
  if array[hi] == value then return hi
  mid = (hi + lo) / 2
  if array[mid] == value then return mid
  if (mid > 0 & array[mid-1] < array[mid])
     | (mid < array.length-1 & array[mid+1] > array[mid]) then
    # max is to the right of mid
    bin = binary_search(array, value, low, mid-1)
    if bin != -1 then return bin
    return bitonic_search(array, value, mid+1, hi)
  else # max is to the left of mid
    bin = binary_search(array, value, mid+1, hi)
    if bin != -1 then return bin
    return bitonic_search(array, value, lo, mid-1)        

因此,时间的递归公式是f(l) = f(l/2) + log(l/2) + c,其中log(l/2)来自二进制搜索,c是在函数体中进行比较的成本。

票数 1
EN

Stack Overflow用户

发布于 2014-03-16 20:49:54

所提供的答案的时间复杂度为(N/2)*logN。因为最坏的情况可能包括太多的子搜索,这是不必要的。修改是在搜索前将目标值与子序列的左、右元素进行比较。如果目标值不是在单调序列的两端之间,或者小于双元序列的两端,则后续搜索是多余的。这种修改导致了2lgN的复杂性。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/19372930

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档