algorithm - それ以降のすべての要素が指定された値よりも大きいように、並べ替えられた配列内の要素を見つける方法は?

Question

二分探索アルゴリズムを改変して実装してみました。

int search(int *a, int start,int end,int sum){
int s=start,e=end-1,m;
while(s <= e){
    m=s+(e-s)/2;
    if(a[m] == sum){
        return m+1;            
    }
    else if (a[m] < sum) {
        s = m + 1;
    }
    else {
        e = m - 1;
    }
}
return m;}

上記のアルゴリズムの何が問題になっていますか?

Answer 1

int search(int *a, int start,int end, int sum) {
    int s = start, e = end - 1, m;
    while(s <= e) {

もっと簡単なのは

    // m=s+(e-s)/2;
    m=(s+e)/2;

ループし続ける必要があります。繰り返し要素がある可能性があります

//            if(a[m] == sum){
//                return m+1;            
//            } else

に変更された条件に注意してください<=

//      if (a[m] < sum) {
        if (a[m] <= sum) {
            s = m + 1;
        }
        else {
            e = m - 1;
        }
    }

sここに戻らなければならない

//  return m;
    return s;
}