4

すでにソートされている配列から数値 X の床と天井を見つけます。例えば

[] = {3、7、9、10、15}

  • X=2 の場合、下限 = N/A、上限 = 3
  • X=3 の場合、床 = 3、天井 = 3
  • X=4 の場合、床 = 3、天井 = 7
  • X=16 の場合、床 = 15、天井 = N/A

私たちのほとんどは解決策について知っていると思います。つまり、修正された二分探索によって床/天井を見つけることができます。しかし、修正二分探索の問題は、多くの境界条件を処理する必要があることです。しかし、同じバイナリ検索アルゴリズムが機能することを発見しましたが、フロアの場合は単に書き込む必要がif low > high return low あり、 ceil のif low > high return high場合は. また、floor が -1 を返す場合は N/A を表示し、ceil が配列インデックスよりも大きい値を返す場合は N/A を表示します。

フロアのアルゴリズム:

int floorSearch(int a[], int low, int high, int x)
{
    if(low > high){
        return low;
    }
    int mid = (low+high)/2;
    if(a[mid]>x){
        return floorSearch(a, low, mid-1, x);
    }
    else if(a[mid]<x){
        return floorSearch(a, mid+1, high, x);
    }
    else{
        return mid;
    }
}

そしてceilの場合：

int ceilSearch(int a[], int low, int high, int x)
{
    if(low > high){
        return high;
    }
    int mid = (low+high)/2;
    if(a[mid]>x){
        return ceilSearch(a, low, mid-1, x);
    }
    else if(a[mid]<x){
        return ceilSearch(a, mid+1, high, x);
    }
    else{
        return mid;
    }
}

とても簡単ですね。多くの入力を確認しましたが、機能しますが、アルゴリズムの正確性を証明できませんでした。誰かが正しいことを証明するために試してみることができますか、またはこのアルゴリズムが失敗するサンプル入力を与えることもできます. ありがとう。

4

4 に答える 4

1

証明方法のヒント:

  1. これらのアルゴリズムの正しさの証明は、アルゴリズムの再帰構造に従います。つまり、構造帰納法による証明を使用します（調べてください）。

  2. 標準的な二分探索の証明を見て、それがどのように構成されているかを理解してください。

  3. コードにバグがある場合は、正しい証拠を見つけられないはずです。他のコメントと他の回答を参照してください。

于 2013-09-13T01:41:14.987 に答える
1

コードには従来のバグがあります。を使用していますint mid = (low+high)/2;。配列が非常に大きい場合、加算が負の結果にオーバーフローして mid が負になる可能性があります。

このバグはint mid = (low+high)>>>1;、java.util.Arrays の binarySearch メソッドで行われるように、 を使用して修正できます。は>>> 1、事実上、符号なしの 2 除算を行います。

于 2013-09-13T02:05:26.647 に答える
0

条件を変更しただけなのでif(low > high)、通常の二分探索と同等であることに注意してください。二分探索の証明を理解すると、ここで正しさを判断することはほとんど簡単になります。

于 2013-09-13T01:44:20.073 に答える
0

これは、ceilSearch のコードを壊すテスト ケースです。

a={3, 7, 9, 11, 13}, x=10.

各再帰呼び出しで低、高、中をリストしています。

(0, 4, 2) -> a[2]=9 < x

(3, 4, 3) -> a[3]=11 > x

(3, 2, 2) -> 低 > 高、低 = 2 を返します。

正解は 2 ではなく 3 です。

于 2018-01-29T13:22:05.713 に答える