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;
}

私がこの質問をする理由は、私が 2 つのことを疑問に思っているからです。1）「14」などの一部の値で失敗するため、コードの何が問題になっていますか。2)改善できますか?

Answer 1

あなたのコードでは、「if」操作のような多くの分岐があると思います。以下は、参照用の簡単な擬似コードです。

while(1 < (high - low)){
     int mid = (low + high) >> 1;
     (key < A[mid]) ? high = mid : lo = mid;
}
return (key == A[lo]) ? lo : -1;

これがお役に立てば幸いです。