在Java中使用Arrays.binarySearch()的例子（在子数组中搜索）

Arrays.binarySearch() | 第1集讲解如何在Java中找到排序数组中的元素。本集将涵盖“如何在给定范围内包括仅起始索引在数组中搜索关键字”。

语法：

public static int binarySearch(data_type[] arr, int fromIndex, int toIndex, data_type key)

参数：

arr - 要搜索的数组

fromIndex - 要搜索的第一个元素（包括）的索引

toIndex - 要搜索的最后一个元素（不包括）的索引

key - 要搜索的值

这是一个静态内置方法，由Java的Arrays（java.util.Arrays）类定义，如果在指定范围内找到指定的关键字，则返回索引。
在这里， data_type 可以是任何原始数据类型：byte，char，double，int，float，short，long和Object。
上述函数使用二进制搜索算法搜索给定数据类型的指定数组的范围中指定的关键字。
所要搜索的范围必须在此调用之前排序（如Arrays.sort()方法）。否则，结果将是未定义的。如果指定数组包含多个与指定关键字相同的值，则无法保证找到哪个值。

返回值：

在指定数组的指定范围内找到指定关键字的索引，否则为（-（插入点） – 1）。

插入点被定义为指定关键字将插入的点：范围内第一个大于关键字的元素的索引，或者如果范围内的所有元素都小于指定的关键字，则为toIndex。

注意：这保证返回值只有在找到关键字时才会> = 0。

例子：

byteArr[] = {10,20,15,22,35}

key = 22将在指定数组的范围2到4之间进行搜索。

输出：3

charArr[] = {‘g’，’p’，’q’，’c’，’i’}

key = p将在指定数组的范围1到4之间进行搜索。

输出：3

intArr[] = {1,2,3,4,5,6}

key = 3将在指定数组的范围1到4之间进行搜索。

输出：2

doubleArr[] = {10.2,1.51,2.2,3.5}

key = 1.5将在指定数组的范围1到4之间进行搜索。

输出：-2，因为它是1.5的插入点

floatArr[] = {10.2f,15.1f,2.2f,3.5f}

key = 35.0将在指定数组的范围1到4之间进行搜索。

输出：-5

shortArr[] = {10,20,15,22,35}

key = 5将在指定数组的范围0到4之间进行搜索。

输出：-1

实现：

// Java程序演示在排序数组的指定范围内使用binarySearch()方法的工作。
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[] = { 1, 2, 3, 4, 5, 6 };
        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(byteArr);
        Arrays.sort(charArr);
        Arrays.sort(intArr);
        Arrays.sort(doubleArr);
        Arrays.sort(floatArr);
        Arrays.sort(shortArr);

        byte byteKey = 22;
        char charKey = 'p';
        int intKey = 3;
        double doubleKey = 1.5;
        float floatKey = 35;
        short shortKey = 5;

        System.out.println(
            byteKey + " found at index = "
            + Arrays.binarySearch(byteArr, 2, 4, byteKey));
        System.out.println(
            charKey + " found at index = "
            + Arrays.binarySearch(charArr, 1, 4, charKey));
        System.out.println(
            intKey + " found at index = "
            + Arrays.binarySearch(intArr, 1, 4, intKey));
        System.out.println(doubleKey + " found at index = "
                                   + Arrays.binarySearch(
                                       doubleArr, 1, 4, doubleKey));
        System.out.println(floatKey + " found at index = "
                                   + Arrays.binarySearch(
                                       floatArr, 1, 4, floatKey));
        System.out.println(shortKey + " found at index = "
                                   + Arrays.binarySearch(
                                       shortArr, 0, 4, shortKey));
    }
}

输出

22 found at index = 3
p found at index = 3
3 found at index = 2
1.5 found at index = -2
35.0 found at index = -5
5 found at index = -1

复杂度分析：

时间复杂度：

Arrays类中binarySearch()方法的时间复杂度用于在指定范围内搜索为O(log n)。在给定的代码中，binarySearch()方法被调用六次，每次使用不同的数组和不同的元素范围。因此，整个代码的时间复杂度将是O(log n) * 6，它可以简化为O(log n) 。

辅助空间复杂度：

binarySearch() 方法不使用任何额外的空间。因此，代码的辅助空间复杂度为O(1) 。

异常：

IllegalArgumentException ：当起始索引（fromIndex）大于指定范围的结束索引（toIndex）时抛出异常（即：fromIndex>toIndex）。
ArrayIndexOutOfBoundsException ：如果一个或两个索引无效，即fromIndex<0或toIndex>arr.length，则抛出异常。

要点：