通用二进制搜索Java

Question

我一直在尝试使这段代码工作.我必须创建二进制搜索的通用二进制版本.我不确定如何在没有类似界面的情况下比较两种泛型类型

import java.util.ArrayList; 

public class BinarySearcher<T> {
    private T[] a;

    public BinarySearcher(T[] words) {
        a = words;
    }

    public int search(T v) {
        int low = 0;
        int high = a.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            T midVal = a[mid];  

            if (v.compareTo(midVal) < 0) {
                low = mid - 1;
            }   

            else if (v.compareTo(midVal) > 0) {
                high = mid  + 1; 
            }
        }

        return -1;
    }

    public int compareTo(T a) {
        return this.value.compare - b;
    }
}

这是测试人员类:

import java.util.Arrays;
import java.util.Scanner;
/**
  This program tests the binary search algorithm.
*/
public class BinarySearchTester {
    public static void main(String[] args) {
        String[] words = {"Alpha", "Bravo", "Charlie", "Delta", "Echo", 
            "Foxtrot", "Golf", "Hotel", "India", "Juliet", "Kilo", "Lima", 
            "Mike", "November", "Oscar", "Papa", "Quebec", "Romeo", 
            "Sierra", "Tango", "Uniform", "Victor", "Whiskey", "X-Ray", 
            "Yankee", "Zulu"};
        BinarySearcher<String> searcher = new BinarySearcher<String>(words);
        System.out.println(searcher.search("November"));
        System.out.println("Expected: 13");
        System.out.println(searcher.search("October"));
        System.out.println("Expected: -1");
    }
}

Answer 1

public class BinarySearcher<T extends Comparable<T>> { ...

这将允许您的BinarySearcher为可以比较的所有内容工作compareTo,这应该是通用的.

Answer 2

您的泛型方法无法比较某些任意类型的两个实例T,而没有任何约束T或有关于如何比较两个Ts的其他信息.

你有几个选择:

添加约束到T:

public class BinarySearcher<T extends Comparable<T>>

或者通过在Comparator<T>你的search方法,其可称为做比较:

public int search(T v, Comparator<T> comp) {
    // ...
    if (comp.compare(v, midVal < 0)) {
    // ...
}

旁注:我会避免compareTo在你的search方法中打两次电话; 你不知道比较这两个对象是否昂贵.而不是这个:

if (v.compareTo(midVal) < 0) {
    low = mid - 1;
}   
else if (v.compareTo(midVal) > 0) {
    high = mid  + 1; 
}

做这样的事情:

int result = v.compareTo(midVal);
if (result < 0) {
    low = mid - 1;
}   
else if (result > 0) {
    high = mid  + 1; 
}