java 通用二进制搜索Java
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5426316/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Generic binary search Java
提问by carlly
I've been trying to make this code work. I have to create a generic binary version of the binary search. I'm not sure how to compare two generic types without the comparable interface
我一直在努力使这段代码工作。我必须创建二进制搜索的通用二进制版本。我不确定如何在没有可比较接口的情况下比较两种泛型类型
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;
}
}
This is the tester class:
这是测试员类：
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");
}
}
回答by Erik
public class BinarySearcher<T extends Comparable<T>> { ...
public class BinarySearcher<T extends Comparable<T>> { ...
This'll allow your BinarySearcher to work for everything that can be compared with compareTo, which should be generic enough.
这将允许您的 BinarySearcher 用于可以与 进行比较的所有内容compareTo，这应该足够通用。
回答by Jesper
There's no way that your generic method can compare two instances of some arbitrary type T, without having any constraints on Tor having information some other way about how to compare two Ts.
您的泛型方法无法比较某个任意类型的两个实例T，而没有任何限制T或有关如何比较两个Ts 的其他方式的信息。
You have a few choices:
你有几个选择：
Add a constraint to T:
添加约束到T：
public class BinarySearcher<T extends Comparable<T>>
Or pass in a Comparator<T>to your searchmethod that can be called to do the comparison:
或者将 a 传递Comparator<T>给您search可以调用以进行比较的方法：
public int search(T v, Comparator<T> comp) {
// ...
if (comp.compare(v, midVal < 0)) {
// ...
}
Side note: I would avoid calling compareTotwo times in your searchmethod; you don't know if comparing the two objects is expensive. Instead of this:
旁注：我会避免compareTo在你的search方法中调用两次；您不知道比较这两个对象是否昂贵。取而代之的是：
if (v.compareTo(midVal) < 0) {
low = mid - 1;
}
else if (v.compareTo(midVal) > 0) {
high = mid + 1;
}
Do something like this:
做这样的事情：
int result = v.compareTo(midVal);
if (result < 0) {
low = mid - 1;
}
else if (result > 0) {
high = mid + 1;
}
回答by o12
Even after doing all the changes suggested above, the Conditions you are using are incorrect (your changing of low and high pointers) and you need an else clause after else if to return the index.
即使在进行了上面建议的所有更改之后，您使用的条件也不正确（您更改低指针和高指针）并且您需要在 else if 之后使用 else 子句来返回索引。
public class BinarySearcher<T extends Comparable<T>> {
private T[] a;
public BinarySearcher(T[] words) {
a = words;
}
public int search(Comparable<T> v) {
int low = 0;
int high = a.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
T midVal = a[mid];
int result = v.compareTo(midVal);
if (result < 0) {
high = mid - 1;
}
else if (result > 0) {
low = mid + 1;
}
else {
return mid;
}
}
return -1;
}
}
回答by Venu
The following class can be used do to binary search for any data type.
以下类可用于对任何数据类型进行二分搜索。
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class GenericBinarySearch{
private int midPoint(int iMin, int iMax){
return iMin + (iMax - iMin)/2;
}
public <T> int search(List<T> list, T Key, int iMin, int iMax, Comparator<T> comparator){
if(list == null || list.size() == 0){
return -1;
}
int iMid = midPoint(iMin, iMax);
if(iMid > iMax || iMid < iMin){
return -1;
}
if(comparator.compare(list.get(iMid), Key) > 0){
return search(list, Key, iMin, iMid-1, comparator);
}else if(comparator.compare(list.get(iMid), Key) < 0){
return search(list, Key, iMid+1, iMax, comparator);
}else{
return iMid;
}
}
public static void main(String[] args) {
GenericBinarySearch bs = new GenericBinarySearch();
List<Integer> list = new ArrayList<Integer>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
int key = 2;
int iMin = 0;
int iMax = list.size()-1;
//Java 8 - Lambda expressions
// new Comparator( public T int compare(T o1, T o2) {
// return o1.compareTo(o2);
// }) ---> same expression is replaced by
// (T o1, T o2) -> o1.compareTo(o2) or (o1,o2) -> o1.compareTo(o2)
int index = bs.search(list, key, iMin, iMax, (o1,o2) -> o1.compareTo(o2));
System.out.println(index);
}
}
回答by pajton
It is impossibleto compare types that do not implement Comparableinterface. Not by using compareTo().
这是不可能的，比较不实现类型的Comparable接口。不是通过使用compareTo().
回答by lukastymo
Try this:
试试这个：
class BinarySearcher<T extends Comparable<T>>
回答by Stephen C
@Erik's answer shows how to modify your code so that it requires that the parameter type Tis comparable.
@Erik 的回答显示了如何修改您的代码，以便它要求参数类型T具有可比性。
The other alternative is to use a Comparator<T>; e.g.
另一种选择是使用Comparator<T>; 例如
import java.util.ArrayList;
public class BinarySearcher<T> {
private T[] a;
private Comparator<T> c;
public BinarySearcher(T[] words, Comparator<T> comparator) {
a = words;
c = comparator;
}
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 (c.compare(v, midVal) < 0) {
low = mid - 1;
}
else if (c.compare(v, midVal) > 0) {
high = mid + 1;
}
}
return -1;
}
}
You couldcombine the two approaches by modifying the original constructor to use a comparator that casts the first values it wants to compare to Comparableinstances. This will probably doing an unsafe conversion, and will result in a ClassCastExceptionif the actual type corresponding to T is not actually a Comparable.
您可以通过修改原始构造函数以使用比较器来组合这两种方法，该比较器将要与Comparable实例进行比较的第一个值进行转换。这可能会进行不安全的转换，ClassCastException如果对应于 T 的实际类型实际上不是 a ，则会导致a Comparable。
From a design perspective, it would be a better idea if the BinarySearcherconstructor either checked that wordswas sorted, or sorted the array itself. Binary search will give the wrong answer if wordsis not properly ordered.
从设计的角度来看，如果BinarySearcher构造函数要么检查words已排序，要么对数组本身进行排序，这将是一个更好的主意。如果words排序不正确，二分搜索将给出错误的答案。
回答by Mr. Slash
As the others already mentioned leting T extends Comparable would solve your issue. Buuuut why are you reinventing the wheel? You could easily use the existing generic Java Binary Search:
正如其他人已经提到的，让 T 扩展 Comparable 可以解决您的问题。Buuuut 你为什么要重新发明轮子？您可以轻松使用现有的通用 Java 二进制搜索：
System.out.println(Arrays.binarySearch(words, "November", null));
Note that if null is passed as comparable parameter, the natural element order is taken!
请注意，如果 null 作为可比较参数传递，则采用自然元素顺序！
Enjoy!
享受！
