javaで2分木探索(binarySearch)

binarySearchという、collectionsライブラリにあるメソッドを使ってjavaで2分木探索を行う方法を紹介します。

listに重複があるかどうかで実装方法が変わってきます。

Listに重複がない場合

この場合はCollections.binarySearchを使えば簡単に求まります。

存在しない場合は(-(挿入場所) - 1)が返ります。

    public static void main(String args []) {

        List<Integer> list = Arrays.asList(1, 2, 3, 4, 6, 9);

        //探索したいint
        int key = 4; 

        //list上の位置。　なければ負の値が返る
        int position = Collections.binarySearch(list, key);

        //keyが4の場合は、3
        //keyが5の場合は、-5
       //5の挿入場所は4なので、(-4 - 1)が返ります
        System.out.println(position);  
    }

Listに重複するものがある場合(なくても良い)

この場合はCollections.binarySearchの引数の3番目、Comparatorを使います。

    public static void main(String args[]) {

        List<Integer> list = Arrays.asList(1, 2, 2, 3, 4, 4, 4, 6, 9);

        int key = 4;

        int check = Collections.binarySearch(list, key);  //(1)

        if (check < 0) {
            System.out.println("not exist");
        } else {
            //lower_bound
            int lowerPosition = ~Collections.binarySearch(list, key, (x, y) -> x.compareTo(y) >= 0 ? 1 : -1); //(2)
            System.out.println(lowerResult);// => 4
            //upper_bound
            int upperPosition = ~Collections.binarySearch(list, key, (x, y) -> x.compareTo(y) > 0 ? 1 : -1);  //(3)
            System.out.println(upperResult);// => 7
        }

    }

(1) まずは、探索したい数がlistに存在するか確かめます。
checkが負ならば、存在しないということになります。

(2)key以上の数が始めて現れる位置を返します。
負で返されるので、反転の~を先頭に付けています。

(3)keyより大きい数が初めて現れる位置を返します。

重複して存在する場合は 、lowerPositionからupperPosition-1までkeyが存在することになります。

keyが4の場合は4から6の位置まで存在することになります。(最初の位置はもちろん0です)

もし重複していない場合はlowerPosition = upperPosition -1 になります。

以上がライブラリを使ったjavaで二分木探索をする方法です。