算法：改进的二进制搜索 [英] Algorithm: Modified Binary Search

问题描述

我试图解决它基本上执行一个列表，其中先增加后减少的二进制搜索一个经典面试问题。虽然很明显，我们可以实现 O（log n）的我​​无法弄清楚什么是错的code以下，我已经写了：

I am trying to tackle a classical interview problem which is basically performing a binary search on a list which first increases then decreases. Even though it's obvious that we can achieve O(log n) I couldn't figure out what is wrong the code below that I've written:

#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有什么不对与code。 2），可以改进？

The reason why I ask this question is because I wonder two things. 1) What is wrong with the code since it fails for some values such as "14". 2) Can it be improved?

推荐答案

我觉得你的code没有处理好数组的增加和减少的部分。

I think your code does not handle well the increasing and decreasing part of the array.

不是告诉你究竟是如何做到这一点，这里有一些技巧，我希望你能完成它：）

Instead of telling you exactly how to do this, here is some tip and I hope you are able to finish it :)

一种解决方案是先找到其中数组去从提高以在O（LOGN）降序排列的点，则此基础上，在O（LOGN）执行二进制搜索的一个特殊版本。

One solution is to first find the point where the array goes from increasing order to decreasing order in O(logn), then based on that, perform a special version of binary search in O(logn).

让我知道，如果你不知道如何应对，我会介绍一些关于我的答案。

Let me know in case you don't know how to to this, I will explain more on my answer.

这篇关于算法：改进的二进制搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！