無秩序(ソートされていない)配列二分検索

二分検索は折半検索とも呼ばれます(Binary Search)は、効率の高い検索方法です.しかし、半減検索では、線形テーブルは順序格納構造を採用しなければなりません.また、テーブル内の要素はキーワード順に並べられています.しかし、無秩序配列については、まず2点に並べ替えることができますが、速い配列の考え方を組み合わせることもできます.つまり、キーワードを選択するたびに、彼より大きい数を先に置くことです.その右側、彼より小さい数を左側に置いて、検索する数との関係を比較し、次の反復の区間を選択します.

public class BinarySearch {

    /**
     *         
     * @param arr
     * @param left
     * @param right
     * @param key
     * @return
     */
    public static int binarySearch(Integer[] arr, int left, int right, Integer key) {
        if(left < right) {
            int partition = partition(arr, left, right);
            if(key < arr[partition]) {
                return binarySearch(arr, left, partition - 1, key);
            } else if (key > arr[partition]) {
                return binarySearch(arr, partition + 1, right, key);
            } else {
                return partition;
            }
        }
        return 0;
    }

    /**
     *          
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public static int partition(Integer[] arr, int left, int right) {
        int temp = left - 1;
        for(int i = left; i < right; i++) {
            if(arr[i] < arr[right]) {
                temp++;
                swap(arr, temp, i);
            }
        }
        swap(arr, temp + 1, right);
        return temp + 1;
    }

    /**
     *       
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(Integer[] arr, int i, int j) {
        Integer temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args){

        Integer[] arr = {8, 6, 2, 3, 2, 9, 1, 5, 7};
        System.out.println(binarySearch(arr, 0 ,arr.length - 1, 2));
        System.out.println(Arrays.asList(arr));

    }

}