Java中的Arrays.binarySearch()方法及示例

Arrays.binarySearch() 方法使用二分查找算法在指定的给定数据类型的数组中搜索指定的值。在调用此方法之前，数组必须按Arrays.sort()方法进行排序。如果没有排序，则结果是未定义的。如果数组包含多个具有指定值的元素，则不能保证找到哪个元素。下面让我们通过提供的案例来浏览说明。

说明：

在byteArr[] = {10,20,15,22,35}中查找35
将会得到结果4，因为它是35的索引

在charArr[] = {‘g’,’p’,’q’,’c’,’i’}中查找g
将会得到结果0，因为它是’g’的索引

在intArr[] = {10,20,15,22,35}中查找22
将会得到结果3，因为它是22的索引

在doubleArr[] = {10.2,15.1,2.2,3.5}中查找1.5
将会得到结果-1，因为它是1.5的插入点

在floatArr[] = {10.2f,15.1f,2.2f,3.5f}中查找35.0
将会得到结果-5，因为它是35.0的插入点

在shortArr[] = {10,20,15,22,35}中查找5
将会得到结果-1，因为它是5的插入点

这是在Java中查找已排序数组中元素的最简单、最有效的方法。

语法：

public static int binarySearch(data_type arr, data_type key)

注意： 这里数据类型可以是任何原始数据类型，如byte、char、double、int、float、short、long，甚至是对象类型。

参数：

要搜索的数组
要搜索的值

返回类型： 搜索关键字的索引，如果它包含在数组中；否则返回(-（插入点）-1)。插入点定义为将键插入数组的位置：大于键的第一个元素的索引，或a.length，如果所有元素都小于指定的键。注意，这保证了如果且仅当找到键时，返回值会>=0。

必须记住以下一些重要点：

如果输入列表未排序，则结果是未定义的。
如果有重复项，则不能保证找到哪个元素。

如上所述，我们可以使用以下算法运行此算法 Arrays.binarysearch() vs Collections.binarysearch() . Arrays.binarysearch()适用于原始数据类型也可以。Collections .binarysearch()适用于对象集合，如ArrayList和LinkedList。

示例1：

// Java程序演示数组的工作。 在排序数组中使用binarySearch()
// 从java.util包导入Arrays类
import java.util.Arrays;
 
// 主类
public class GFG {
// 主驱动程序方法
    public static void main(String[] args)
    {
        // 声明和初始化要搜索的字节数组
        byte byteArr[] = { 10, 20, 15, 22, 35 };
        char charArr[] = { 'g', 'p', 'q', 'c', 'i' };
        int intArr[] = { 10, 20, 15, 22, 35 };
        double doubleArr[] = { 10.2, 15.1, 2.2, 3.5 };
        float floatArr[] = { 10.2f, 15.1f, 2.2f, 3.5f };
        short shortArr[] = { 10, 20, 15, 22, 35 };
 
        // 使用Arrays类的sort()方法并将要排序的数组作为参数传递
        Arrays.sort(byteArr);
        Arrays.sort(charArr);
        Arrays.sort(intArr);
        Arrays.sort(doubleArr);
        Arrays.sort(floatArr);
        Arrays.sort(shortArr);
 
        //原始数据类型
        byte byteKey = 35;
        char charKey = 'g';
        int intKey = 22;
        double doubleKey = 1.5;
        float floatKey = 35;
        short shortKey = 5;
 
        //在排序数组中获取元素/索引并返回
        //访问索引以显示数组是真正排序的
        //是实现的打印命令
        System.out.println(
            byteKey + " found at index = "
            + Arrays.binarySearch(byteArr, byteKey));
        System.out.println(
            charKey + " found at index = "
            + Arrays.binarySearch(charArr, charKey));
        System.out.println(
            intKey + " found at index = "
            + Arrays.binarySearch(intArr, intKey));
        System.out.println(
            doubleKey + " found at index = "
            + Arrays.binarySearch(doubleArr, doubleKey));
        System.out.println(
            floatKey + " found at index = "
            + Arrays.binarySearch(floatArr, floatKey));
        System.out.println(
            shortKey + " found at index = "
            + Arrays.binarySearch(shortArr, shortKey));
    }
}

输出

35 found at index = 4
g found at index = 1
22 found at index = 3
1.5 found at index = -1
35.0 found at index = -5
5 found at index = -1

复杂度分析:

时间复杂度:

Arrays.binarySearch()方法的时间复杂度为O(log n)，其中n是输入数组的长度。这是因为该方法使用二进制搜索算法在排序后的数组中查找目标元素。

辅助空间:

Arrays.binarySearch()方法使用的辅助空间为O(1)，因为它除了需要执行搜索操作的输入数组之外，不需要任何额外的空间。

还有该方法的变体，可以在其中指定要搜索的数组范围。我们将在进一步的帖子中讨论该主题以及在对象数组中执行搜索。

示例2：

// Java程序，用于说明集合类中binarySearch()方法

// 导入所需的类
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

// 主类
public class GFG {

    // 主驱动方法
    public static void main(String[] args)
    {

        // 创建空列表
        List<Integer> al = new ArrayList<Integer>();

        // 将元素添加到列表中
        al.add(12);
        al.add(53);
        al.add(23);
        al.add(46);
        al.add(54);

        // 使用Collections类的binarySearch()方法
        // 在随机插入的元素上存储索引
        int index = Collections.binarySearch(al, 23);

        // 打印并展示索引
        System.out.print(index);
    }
}

输出

复杂度分析：

时间复杂度：

集合类中binarySearch()方法的时间复杂度为O(log n)，其中n是列表中的元素数。

辅助空间：

集合类中的binarySearch()方法不需要任何额外空间，因此其辅助空间复杂度为O(1)。