indexOf还是二进制搜索？ [重复]

4 回答

• 2

  您可以直接使用 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）时间运行，但不关心列表是否已排序 .

  回复于 2024-04-20T10:06:24+08:00
• 0

  如果它已排序，那么你应该使用binarysearch . binarySearch（）将是O（log n）而不是indexOf（）的O（n）

  回复于 2024-04-20T10:06:24+08:00
• 0

  这取决于你究竟在寻找什么 . 假设你在数组列表中有以下字符串：“a”，“b”，“c”，“d”，“e”，“f”，“g”，“h”，“i”你的二进制搜索会在一棵看起来像树的树下工作

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

  因此，根据您搜索的字符串，您将获得不同的尝试次数，直到找到正确的字符串 . 随着算法工作，它从顶部向下，并比较搜索的字符串是大于还是小于它正在测试的字符串，并根据检查字符串向左（较小）或向右（较大）

  但是，如果你想要自己下线并且没有搜索排序列表开头的内容，那么搜索将花费更长时间 .

  回复于 2024-04-20T10:06:24+08:00
• 0

  已经提到二进制搜索更好，因为它使用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);
  

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

  回复于 2024-04-20T10:06:24+08:00