迹忆客 专注技术分享

Java Collections 类有一个名为 binarySearch() 的内部方法，它返回对象在排序列表中的位置。 Collections binarySearch() 函数的参数允许根据脚本的不同参数进行区分。

Collections.binarySearch() 使用二分搜索算法在提供的列表中搜索所请求的对象。 Before进行此调用之前，必须使用其项目的自然顺序按升序对列表进行排序。

如果不排序，结果就不清楚。 如果列表包含许多与请求的对象相同的元素，则无法确定是否会找到所需的元素。

二分查找的基本算法

在二分查找中，集合被反复分成两半。 根据关键元素是小于还是大于集合的中间元素，在集合的左半部分或右半部分中搜索关键元素。

二分搜索算法中要遵循的步骤：

1. 确定集合的中点。
2. 将中间元素与基本组件进行比较。
3. 如果键与中间元素相同，则返回发现的键的中间索引位置。
4. 否则，如果 key > mid 元素，则 key 位于集合的右半部分。 重复步骤 1 到 3 以完成集合的下（右）半部分。
5. 如果键是中间元素，则键位于集合的上半部分。 结果，必须在上半部分再次进行二分查找。

Java 中 Collections.binarySearch() 的语法

以下语法用于声明此方法。

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

Collections.binarySearch() 方法有两种类型：

1. Java 集合 binarySearch(List<? extends Comparable<? super T>> list, T key)。

   在使用该过程之前，必须使用提供的自然数按升序排列列表。 如果列表未排序，则结果是不可定义的。

2. Java 集合 binarySearch(List<? extends T> list, T key, Comparator<? super T> c)。

   在调用该过程之前，必须使用提供的比较器按升序排列列表。

在 Java 中使用 Collections.binarySearch() 的搜索类型

为了使 binarySearch() 按预期运行，您的数据必须按提供的比较器排序。 在进行此调用之前，必须使用提供的比较器按升序对列表进行排序。

如果数据已排序，该过程将提供所需元素的索引； 否则，它将返回 (-(插入点) - 1)。

在升序列表中搜索整数键。

示例代码：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
  
public class Main {
    public static void main(String[] args)
    {
        List<Integer> al = new ArrayList<Integer>();
        al.add(3);
        al.add(4);
        al.add(5);
        al.add(20);
        al.add(30);
   
        int index = Collections.binarySearch(al, 20);
        System.out.println(index);
       
        index = Collections.binarySearch(al, 12);
        System.out.println(index);
    }
}

输出:

3
-4

在降序列表中搜索整数键。

示例代码：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
  
public class Main {
    public static void main(String[] args)
    {
        List<Integer> al = new ArrayList<Integer>();
        al.add(350);
        al.add(90);
        al.add(45);
        al.add(20);
        al.add(3);
  
  
        int index = Collections.binarySearch(
            al, 45, Collections.reverseOrder());
  
        System.out.println(index);
    }
}

输出:

2

总结

Collections binarySearch() 是最流行的搜索方法。 这里的条件是数据必须按升序排序才能使二分查找成功。

迭代或递归方法都可以用来实现二分搜索。 Java Arrays 类还提供了 binarySearch() 方法，该方法对数组进行二分搜索。