探索のアルゴリズム：二分探索（バイナリサーチ）

1. 配列の中心のデータと探索値を比較
2. データが一致した場合、探索終了。
3. 一致しなかった場合、比較した値の大小により、データを半分に絞る。
4. はじめに戻り、繰り返す。

class Search{
    /*
    * 二分探索
    * 引数１：数値配列    引数２：探索データ
    * 戻り値：見つかった場合データの要素番号
    *         見つからなかった場合 -1
    */
    public static int binarySearch(int[] d, int x){
        int lo = 0;
        int hi = d.length - 1;
        int mid = (lo + hi) / 2;

        //探索
        while(lo <= hi && d[mid] != x){
            if(d[mid] > x){
                hi = mid - 1;
            }else{
                lo = mid + 1;
            }

            mid = (lo + hi) / 2;
        }

        //結果返却
        if(lo <= hi){
            return mid;
        }else{
            return -1;
        }
    }
}