java中有序列表中的二分查找
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/18110619/
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
Binary search in an ordered list in java
提问by JsMartinez
Im looking for a way to implement a code in java that works the same way as a binary search in an ordered ArrayList but for an ordered List Thanks
我正在寻找一种在 java 中实现代码的方法，它的工作方式与有序 ArrayList 中的二进制搜索相同，但对于有序列表，谢谢
采纳答案by gr3co
The algorithm should be the same for both an ArrayListand a List, given they are both ordered.
anArrayList和 a的算法应该相同List，因为它们都是有序的。
回答by Saher Ahwal
You should also remember that you cannot do binary search if the list is not ordered. It doesn't make sense. Binary search is O(log n)because you can at every point disregard half of the list since you have knowledge that it is ordered. If the list is not ordered, then your search is O(n) and you cannot use binary.
您还应该记住，如果列表未排序，则不能进行二分查找。这没有意义。二分搜索是O(log n)因为您可以在任何时候忽略列表的一半，因为您知道它是有序的。如果列表没有排序，那么您的搜索是 O(n) 并且您不能使用二进制。
your own implementation for binary search should look like this:
您自己的二分搜索实现应如下所示：
int binary_search(int A[], int key, int imin, int imax)
{
// test if array is empty
if (imax < imin)
// set is empty, so return value showing not found
return KEY_NOT_FOUND;
else
{
// calculate midpoint to cut set in half
int imid = midpoint(imin, imax);
// three-way comparison
if (A[imid] > key)
// key is in lower subset
return binary_search(A, key, imin, imid-1);
else if (A[imid] < key)
// key is in upper subset
return binary_search(A, key, imid+1, imax);
else
// key has been found
return imid;
}
}
source: Wikipedia
来源：维基百科
If you want to use Java.util implementation then use:
如果要使用 Java.util 实现，请使用：
java.util.Arrays.binarySearch(int[] a, int key)
Array ashould be sorted of course.
数组a当然应该排序。
回答by ajb
"Binary search" only makes sense if the elements of the list (or some kind of pointers to the elements) are organized sequentially in memory, so that if know that your search has been narrowed down to indexes Low and High, you can jump right to the element at (Low + High) / 2 without having to slog through all the other elements. This isn't going to work for a general List, which could be a LinkedList. For something like that, you can't really do better than starting at the front of the list and going through all the elements in order.
“二进制搜索”只有在列表的元素（或某种指向元素的指针）在内存中按顺序组织时才有意义，这样如果知道您的搜索范围已缩小到索引低和高，您可以向右跳转到 (Low + High) / 2 处的元素，而无需遍历所有其他元素。这不适用于一般列表，它可能是 LinkedList。对于这样的事情，你真的不能比从列表的前面开始并按顺序浏览所有元素做得更好。
回答by zapl
You can use
您可以使用
Collections.<T>binarySearch(List<T> list, T key)
Collections.<T>binarySearch(List<T> list, T key)
for binary search on any List. It works on ArrayListand on LinkedListand on any other List.
用于对任何List. 它的工作原理上ArrayList和LinkedList和其他List。
However:
然而：
binary search is only fast if you have direct access to each element:
如果您可以直接访问每个元素，二进制搜索只会很快：
This method runs in log(n) time for a "random access" list (which provides near-constant-time positional access). If the specified list does not implement the RandomAccess interface and is large, this method will do an iterator-based binary search that performs O(n) link traversals and O(log n) element comparisons.
此方法在 log(n) 时间内运行，用于“随机访问”列表（提供近乎恒定时间的位置访问）。如果指定的列表未实现 RandomAccess 接口并且很大，则此方法将执行基于迭代器的二进制搜索，执行 O(n) 链接遍历和 O(log n) 元素比较。
If your Listdoes not provide "random access" you might have better luck by creating a copy of that Listthat does provide this.
如果您List不提供“随机访问”，您可能会通过创建List提供此功能的副本来获得更好的运气。
LinkedList<String> list = new LinkedList<String>();
// fill
Either like so
要么像这样
ArrayList<String> fastList = new ArrayList<String>(list);
Collections.binarySearch(fastList, "Hello World");
or maybe like so
或者像这样
String[] array = list.toArray(new String[list.size()]);
Arrays.binarySearch(array, "Hello World");
If your Listis not ordered by default and you have to sort it prior to searching you might get the best result by doing it with arrays since
如果List默认情况下您没有排序并且您必须在搜索之前对其进行排序，则通过使用数组进行排序可能会获得最佳结果，因为
Collections.sort(list);
creates a temporary array that is sorted and used to re-create the list which you should be able to prevent if you do it with arrays directly.
创建一个临时数组，该数组已排序并用于重新创建列表，如果您直接使用数组进行操作，您应该能够阻止该列表。
String[] array = list.toArray(new String[list.size()]);
Arrays.sort(array);
Arrays.binarySearch(array, "Hello World");
