24

首先，这个问题的双调数组被定义为这样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)，这要容易得多。一次更改二进制搜索以找到最大值的索引，然后分别对 0 到 K 和 K + 1 到 N - 1 进行两次二进制搜索。

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

4

8 回答 8

53

不幸的是，其他答案（this和this）中提出的算法不正确，它们不是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。

这是时间~2logN的双音搜索的完整工作实现（在 C++ 中） ：

#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;
}
于 2014-06-07T15:39:11.290 回答
1

该算法通过结合双调和二分搜索递归地工作：

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是在函数体中进行比较的成本。

于 2013-10-15T04:13:50.583 回答
0

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

于 2014-03-16T20:49:54.020 回答
0

有 5 种主要情况，具体取决于数组的最大元素在哪里，以及中间元素是否大于期望值

计算中间元素。比较中间元素所需的值，如果它匹配搜索结束。否则进行下一步。

  1. 将中间元素与邻居进行比较以查看最大元素是在左侧还是右侧。如果两个邻居都小于中间元素，则数组中不存在元素，因此退出。（问题中提到的数组将首先遇到这种情况，因为最大元素 14 位于中间）

  2. 如果中间元素小于期望值并且最大元素在右侧，则在右侧子数组中进行双调搜索

  3. 如果中间元素小于期望值并且最大元素在左侧，则在左侧子数组中进行双调搜索

  4. 如果中间元素大于期望值并且最大元素在左侧，则在右侧子数组中进行降序二分查找

  5. 如果中间元素大于期望值并且最大元素在右侧，则在左侧子数组中进行升序二进制搜索

在最坏的情况下，每次将数组分成两半时，我们将进行两次比较，因此复杂度将为 2*logN

于 2016-12-13T20:25:02.297 回答
0 
    public int FindLogarithmicGood(int value)
    {
        int lo = 0;
        int hi = _bitonic.Length - 1;
        int mid;
        while (hi - lo > 1)
        {
            mid = lo + ((hi - lo) / 2);
            if (value < _bitonic[mid])
            {
                return DownSearch(lo, hi - lo + 1, mid, value);
            }
            else
            {
                if (_bitonic[mid] < _bitonic[mid + 1])
                    lo = mid;
                else
                    hi = mid;
            }
        }

        return _bitonic[hi] == value 
            ? hi
            : _bitonic[lo] == value 
                ? lo
                : -1;
    }

DownSearch 在哪里

    public int DownSearch(int index, int count, int mid, int value)
    {
        int result = BinarySearch(index, mid - index, value);
        if (result < 0)
            result = BinarySearch(mid, index + count - mid, value, false);
        return result;
    }

和 BinarySearch 是

    /// <summary>
    /// Exactly log(n) on average and worst cases.
    /// Note: System.Array.BinarySerch uses 2*log(n) in the worst case.
    /// </summary>
    /// <returns>array index</returns>
    public int BinarySearch(int index, int count, int value, bool asc = true)
    {
        if (index < 0 || count < 0)
            throw new ArgumentOutOfRangeException();
        if (_bitonic.Length < index + count)
            throw new ArgumentException();

        if (count == 0)
            return -1;

        // "lo minus one" trick
        int lo = index - 1;
        int hi = index + count - 1;
        int mid;
        while (hi - lo > 1)
        {
            mid = lo + ((hi - lo) / 2);
            if ((asc && _bitonic[mid] < value) || (!asc && _bitonic[mid] > value))
                lo = mid;
            else
                hi = mid;
        }

        return _bitonic[hi] == value ? hi : -1;
    }

github

于 2017-06-09T07:45:59.290 回答
0

通过标准的二分搜索查找一阶差分之间的符号变化将采用2Lg(n)数组访问。

通过使用称为斐波那契搜索的单峰函数最大值的搜索策略，您可以做得更好。在每个涉及单个查找的 n 步之后，您将区间大小减小一个因子Fn，对应于大约Log n/Log φ ~ 1.44Lg(n)访问以找到最大值。

当数组访问是昂贵的功能评估时，这种边际收益更有意义。

于 2017-08-05T15:16:34.693 回答
0

当涉及在 O(log N) 时间内搜索算法时，您必须只考虑二进制搜索。这里的概念是首先找到峰值点，例如： Array = [1 3 5 6 7 12 6 4 2 ] -> 这里，12 是峰值。一旦检测到并标记为中间，现在只需在 Array[0:mid] 和 Array[mid:len(Array)] 中进行二进制搜索。

注意：从 mid -> len 开始的第二个数组是一个递减数组，需要在二分查找中做一个小的变化。

寻找双调点 :-) [用 Python 编写]

start, end = 0, n-1
while start <= end:
    mid = start + end-start//2
    if (mid == 0 or arr[mid-1] < arr[mid]) and (mid==n-1 or arr[mid+1] < arr[mid]):
    return mid
    if mid > 0 and arr[mid-1] > arr[mid]:
        end = mid-1
    else:
        start = mid+1

找到索引后，进行相应的二进制搜索。呜拉...全部完成:-)

于 2021-07-11T13:31:46.243 回答
-2

对于二元拆分，有以下三种情况：

  1. 最大项目在右边，然后是二进制搜索左边，bitoinc 搜索右边。
  2. 最大项目在左边，然后是二进制搜索右边，bitoinc 搜索左边。
  3. 最大项目正好在分割点，然后左右二进制。

注意：左右使用的二分查找因递增/递减顺序而不同。

public static int bitonicSearch(int[] a, int lo, int hi, int key) {
    int mid = (lo + hi) / 2;
    int now = a[mid];
    if (now == key)
        return mid;
    // deal with edge cases
    int left = (mid == 0)? a[mid] : a[mid - 1];
    int right = (mid == a.length-1)? a[mid] : a[mid + 1];
    int leftResult, rightResult;
    if (left < now && now < right) { // max item is at right
        leftResult = binarySearchIncreasing(a, lo, mid - 1, key);
        if (leftResult != -1)
            return leftResult;
        return bitonicSearch(a, mid + 1, hi, key);
    }
    else if (left > now && now > right) { // max item is at left
        rightResult = binarySearchDecreasing(a, mid + 1, hi, key);
        if (rightResult != -1)
            return rightResult;
        return bitonicSearch(a, lo, mid - 1, key);
    }
    else { // max item stands at the split point exactly
        leftResult = binarySearchIncreasing(a, lo, mid - 1, key);
        if (leftResult != -1)
            return leftResult;
        return binarySearchDecreasing(a, mid + 1, hi, key);
    }
}
于 2014-02-11T09:13:27.277 回答