開発メモ

開発用のメモです。

二分木探査

ソース

package jp.mirageworld.algorithm.search;

import java.util.List;

public class BinarySearch {

    public static <T extends Comparable<T>> boolean container(List<T> list, T target) {
        return container(list, target, 0, list.size());
    }

    public static <T extends Comparable<T>> boolean container(List<T> list, T target, int start, int end) {

        int len = end - start;
        int curr1 = start + len / 2;
        if (len == 0)
            return false;
        T currObj1 = list.get(curr1);
        int compare1 = target.compareTo(currObj1);

        //  1 or 0 or -1
        compare1 = compare1 < -1 ? -1 : compare1 > 1 ? 1 : compare1;

        if (compare1 == 0) {
            return true;
        } else if (compare1 == -1) {
            return container(list, target, start, curr1);
        }
        return container(list, target, curr1 + 1, end);

    }
}

テストケース

package jp.mirageworld.algorithm.search;

import static org.junit.Assert.*;

import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

import jp.mirageworld.algorithm.search.BinarySearch;

import org.junit.Test;

public class BinarySearchTest {

    @Test
    public void testContainer() {
        Set<Long> set = new HashSet<>();
        Long target = Math.round(Math.random() * 500);
        while (set.size() < 500000) {
            set.add(Math.round(Math.random() * 500000D));
        }
        List<Long> list = new LinkedList<>(set);
        target = list.get(target.intValue());

        Collections.sort(list);
        assertEquals(BinarySearch.container(list, target), list.contains(target));
    }

}
Twitter: @asahina_alice