c++ - 算法:改进的二进制搜索

Question

我正在尝试解决一个经典的面试问题，该问题基本上是对先增加然后减少的列表执行二进制搜索。尽管很明显我们可以实现 O(log n)，但我无法弄清楚我编写的以下代码有什么问题:

#include <iostream>

using namespace std;


int binarySearch(int *A, int low, int high, int key)
{
    while(low < high)
    {
        int mid = (low + high) / 2;
        if(key < A[mid])
        {
            if(A[mid - 1] < A[mid] && A[mid] < A[mid + 1])
                high = mid - 1;
            else
                low = mid + 1;
        }
        else if(key > A[mid])
        {
            if(A[mid - 1] < A[mid] && A[mid] < A[mid + 1])
                low = mid + 1;
            else
                high = mid - 1;
        }
        else
            return mid;
    }

    return -(low + 1);
}


int main()
{
    const int SIZE = 8;
    int A[SIZE] = {3,5,7,14,9,8,2,1};
    cout<<binarySearch(A, 0, SIZE, 14);
    return 0;
}

我问这个问题的原因是因为我想知道两件事。 1) 代码有什么问题，因为它对某些值(例如“14”)失败。 2) 能否改进？

Answer 1

我认为您的代码不能很好地处理数组的递增和递减部分。

这里没有告诉您确切的操作方法，而是一些提示，我希望您能够完成它:)

一种解决方案是首先在 O(logn) 中找到数组从升序到降序的点，然后在此基础上执行 O(logn) 中特殊版本的二分查找。

如果您不知道该怎么做，请告诉我，我会在我的回答中做更多解释。