算法:修改二进制搜索

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)中执行特殊版本的二进制搜索.

让我知道,如果您不知道如何做到这一点,我会更多地解释我的答案.