indexOf还是二分查找？

Question

我有一个字符串数组列表，字符串按排序顺序排列，我想找到特定元素的索引，哪种方法更快？

1. 在列表中执行indexOf()。
2. 在等效数组中执行二进制搜索？

- Faske Houton

---

数组列表是否已排序？ - Codor

这是什么编程语言？ - Chris Beck

是的，在字母顺序中 - Faske Houton

实际上它是用Java编写的。 - Faske Houton

为什么要将列表本身的某个操作的性能与“等效数组”上的另一个操作的性能进行比较? 如果列表确实是ArrayList，则可以对其进行二分搜索。此外，尝试一下自己就知道了. - davmac

Answer 1

您可以直接使用Collections.binarySearch来提高效率：

public static <T> int binarySearch(List<? extends Comparable<? super T>> list,
                   T key)

使用二分查找算法在指定的列表中搜索指定的对象。在调用此方法之前，列表必须按其元素的自然顺序（例如通过 sort(List) 方法）以升序排序。如果未排序，则结果是未定义的。如果列表包含多个等于指定对象的元素，则不能保证找到哪一个。
对于“随机访问”列表（提供接近常数时间位置访问），此方法在log(n)时间内运行。如果指定的列表没有实现 RandomAccess 接口并且很大，则此方法将进行基于迭代器的二分搜索，执行 O(n) 链路遍历和 O(log n) 元素比较。
虽然 List.indexOf 运行时间为 O(n)，但它不关心列表是否已排序。

- songyuanyao

Answer 2

如果已经排序，那么应该使用二分查找。binarySearch() 的时间复杂度为 O(log n)，而 indexOf() 的时间复杂度为 O(n)。

- amit dayama

Answer 3

如前所述，二分查找由于其O(log n)的时间复杂度而更好。

另一个好处是Collection.binarySearch(...)返回应插入元素的位置。因此，如果您要进行插入操作，这是另一个优点。以下是其工作原理：

int x = Collection.binarySearch(list, element);
if(x > 0)
     System.out.println("it exists");
else
     list.add(element, -x-1);

我不知道你是否需要这个，但我喜欢它 :)

- smttsp

Answer 4

这取决于您要查找的内容。假设您在数组列表中有以下字符串："a"，"b"，"c"，"d"，"e"，"f"，"g"，"h"，"i"，您的二分搜索将沿着可能看起来像的树向下工作

                           e
                         /   \
                       c       g
                      / \     / \
                    b    d   f    h
                   /               \
                  a                 i

因此，根据您要搜索的字符串不同，您需要不同数量的尝试才能找到正确的字符串。随着算法从顶部向下工作，并比较要搜索的字符串是大于还是小于正在测试的字符串，然后检查左侧（较小）或右侧（较大）的字符串。

但是，如果您沿着行自己往下走，并且您没有搜索已排序列表开头的内容，则搜索将需要更长时间。

- Chawoot

---

这是二分查找运作方式的很好的图示，可以提供一些示例代码来使其更好 ^_^ - user8389458