バイナリナビゲーション

数列のナビゲーション
所定の数列及びナビゲーション対象Xが与えられると、

Xは存在しますか?

X(小さい、小さい、大きい、超える)にはいくつの要素がありますか?

Xに最も近い要素は何ですか?

に表示されます.
ソートされた数列の場合
より速く探索できる方法があります.バイナリ探索です.
バイナリナビゲーション
ソートを保証する配列で、標準X[二分]を使用して範囲を検索します.
O(log N)
昇順配列アレイのプロパティ

の任意のM番インデックスのA[M]値がXより大きい場合、A[M.N]はすべてXより大きい.

の任意のM番インデックスのA[M]値がXより小さい場合、A[1..M]はすべてXより小さい.

注:バイナリ検索は昇順でソートする必要があります.
にぶんたんさく
L:ナビゲート可能な範囲の左端インデックス
R:右端インデックス
Result:Xの位置に移動
ナビゲート先:X以下の要素の一番右側の要素
Nは10万->log(10万)=16万ナビゲーション可能
よく犯す過ち
3位:L、R範囲またはエラー設定Resultの初期値
2位:L、R、M、Result変数の定義を混同して不等号書き間違いを起こす場合
1位:2点探索を行い、並べ替えがなければ
コード#コード#

static int binarySearch(int[] A, int L, int R, int X) {
        /*
         * A[L...R] 에서 X 미만의 수(X 보다 작은 수) 중 제일 오른쪽 인덱스를 return 하는 함수
         * 그런게 없다면 L - 1 을 return 한다.
         */
        int result  = L -1;
        while (L <= R) {
            int mid = (L + R) / 2;
            if (A[mid] < X) {
                result = mid;
                L = mid + 1;
            } else if (A[mid] >= X) {
                R = mid - 1;
            }
        }
        return result;
    }