84.アルゴリズム-二分法検索

二分検索の核心思想は理解が非常に簡単で、分治思想に似ている.すなわち,毎回区間の中間要素と比較することにより,検索対象の区間を半分に縮小し,検索対象の要素が見つかるまで縮小するか,区間を0に縮小し,時間複雑度をO(logn)とする.
二分検索は性能が優れているが、応用シーンも限られている.下位レベルは配列に依存する必要があります.主な理由は、二分ルックアップアルゴリズムが下付きの要素にランダムにアクセスする必要があるためです.2.データが秩序化されていない場合は、まずソートする必要があります.したがって、静的なデータのセットに対して、頻繁に挿入、削除されていない場合は、1回のソート、複数回の二分検索を行うことができます.このようにソートされたコストは均等に割り当てられ、二分検索の境界コストは低くなります.ただし、私たちのデータセットに頻繁な挿入と削除操作がある場合は、二分検索を使用するには、挿入、削除操作のたびにデータが秩序正しく維持されるか、二分検索のたびにソートされます.このような動的データセットに対して,どの方法でも秩序維持のコストが高い.

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
        int target = arr[new Random().nextInt(arr.length)];
        int index = find(arr, target);
        System.out.println(target + " " + index);
    }
 
    /**
     *      arr ,  target
     *     target,       index
     *       target,  -1
     */
    private static int find(int[] arr, int target) {
        return find(arr, target, 0, arr.length - 1);
    }

    private static int find(int[] arr, int target, int l, int r) {
        if (l > r) return -1;
        // int mid = (l+r)/2;
        //             ，         mid
        int mid = l + (r - l) / 2;
        if (target > arr[mid]) {// target mid  
            return find(arr, target, mid + 1, r);
        } else if (target < arr[mid]) {// target mid  
            return find(arr, target, l, mid - 1);
        } else {
            return mid;
        }
    }
}