列表排序时在List中查找值的最佳方法

Question

假设我有一个已排序的Java ArrayList.现在我想找到值x的索引.什么是最快的(不超过30行代码)方式来做到这一点？使用IndexOf()方法？在简单的for循环中迭代所有值？使用一些很酷的算法？我们正在谈论让我们说50个整数键.

Answer 1

二进制搜索,但因为它只有50个项目,谁在乎(除非你必须做数百万次)？简单的线性搜索更简单,50个项目的性能差异可以忽略不计.

编辑:您还可以使用内置的java.util.Collections binarySearch方法.请注意,即使找不到该项,它也会返回一个插入点.您可能需要进行额外的检查,以确保该项目确实是您想要的项目.感谢@Matthew指针.

Answer 2

tvanfosson是对的,任何一个的时间都会非常低,所以除非这个代码非常频繁地运行,否则它不会产生太大的影响.

但是,Java具有用于列表(包括ArrayLists),Collections.binarySearch的二进制搜索的内置功能.