java ArrayList 二进制搜索
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/27375711/
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
ArrayList BinarySearch
提问by user3671459
question
问题
I want to implement a BinarySearch method myself on an Object of Klanthow do i do this?
Klanthas some variables.
我想在一个对象上自己实现一个 BinarySearch 方法，我该Klant怎么做？
Klant有一些变数。
public class Klant {
public String klantID;
private String voornaam;
private String tussenvoegsel;
private String achternaam;
private int leeftijd;
private static boolean MAN = true;
private String plaats;
private String email;
/*
* Getters and setters included
*/
}
Klant toevoeging = new Klant("FirstName", "middleName", "\Lastname\"", 20, false, "Location", "[email protected]");
klanten.add(toevoeging);
回答by Rudi Kershaw
Using Collections.binarySearch(...)
使用 Collections.binarySearch(...)
When you run a Collections.binarySearch(...);on a list the objects in that list must either implementComparable, or you will have to pass a Comparatorinto the binarySearch(...)method;
当您运行Collections.binarySearch(...);的列表上在该列表中必须的对象要么implement可比，否则你将有一个通过比较入binarySearch(...)法;
Using a Comparator as an example you could do the following;
以比较器为例，您可以执行以下操作；
class KlantComparator implements Comparator<Klant> {
@Override
public int compare(Klant o1, Klant o2) {
if(condition)
return 1;
else if(condition2)
return 0;
else
return -1;
}
}
In the above you compare the Klantobjects o1and o2and return 1 if o1should be ranked higher than o2, return 0 if they are the same, and return -1 if o1is ranked lower than o2. And then to run the binary search;
在上面你比较Klant对象o1和o2，如果o1应该排名高于o2，则返回 1 ，如果它们相同，则返回 0，如果o1排名低于，则返回 -1 o2。然后运行二分查找；
KlantComparator kc = new KlantComparator();
ArrayList klants = new ArrayList<Klant>();
Klant o = new Klant();
klants.add(o);
klants.add(new Klant());
klants.add(new Klant());
Collections.sort(klants, kc);
Collections.binarySearch(klants, o, kc);
In the above please note that the klantscollection needs to be sorted first, and that the binarySearch needs to be performed using the same Comparatorthat sorted the list.
在上面请注意需要先对klants集合进行排序，并且需要使用Comparator对列表进行排序的相同来执行 binarySearch 。
I hope this helps.
我希望这有帮助。
Further Reading;
进一步阅读；
回答by Terry Storm
Since you want to implement it yourself, Collections.binarySearchisnt good enough for you?
既然要自己实现，Collections.binarySearch对你来说还不够好？
Okay....
好的....
Binary Search:
二分查找：
you have a sortedlist. Get the element in the middle and compare with the Object in question. if it is lowerthan the element you want to find, repeat the search in the part of the list, which has only higherelements. If it is higher, search in the list part with only lowerelements.
你有一个排序列表。获取中间的元素并与有问题的对象进行比较。如果它低于您要查找的元素，则在列表的部分重复搜索，该部分只有更高的元素。如果较高，则在列表部分中仅搜索较低的元素。
So how do you do binary search?
那么如何进行二分查找呢？
You need a measure, which defines for 2 object what the lower one and what the higher one is.
您需要一个度量，它为 2 个对象定义较低的对象和较高的对象。
Your object must implement Comparableoryou must define a Comparatorfor your list.
您的对象必须实现Comparable或者您必须为您的列表定义一个Comparator。
Then you need to actually sort the list. Sorting would be Collections.sort(myList).
然后您需要对列表进行实际排序。排序将是Collections.sort(myList).
Now List has the size()method, which will help you determine the first "middle" element.
现在 List 有size()方法，它将帮助您确定第一个“中间”元素。
Pseudocode :
伪代码：
**input** : keyElement
startIndex = 0;
endIndex = list.size();
midIndex = (endIndex+startIndex) / 2;
while(list.get(midIndex) != keyElement) {
if (list.get(midIndex) < keyElement) {
startIndex = midIndex;
} else {
endIndex = midIndex;
}
midIndex = (endIndex+startIndex) / 2;
}
return midIndex;
Something along those lines (be careful with boundaries here... maybe a +/-1 is needed.)
沿着这些路线的东西（小心这里的边界......也许需要+/-1。）
