Java binarySearch方法原理详解

什么是binarySearch方法

binarySearch方法是Java Util API提供的的一个静态方法，用于在有序数组中二分查找指定的值。

binarySearch方法原理

binarySearch方法实际上是对比给定值与数组中间值的大小，如果给定值小于中间值，则继续在左半部分递归查找；如果大于，则在右半部分递归查找。这样每次查找的范围都会减半，最终定位到给定值所在的位置。

需要注意的是，这个方法仅适用于有序数组。如果数组是无序的，先要使用sort方法进行排序。

binarySearch方法的语法

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

参数说明：

• arr：指定的数组
• key：要查找的值
• fromIndex：要搜索的第一个元素的索引（包括）
• toIndex：要搜索的最后一个元素的索引（不包括）

返回值：

• 找到了指定元素，返回它的索引
• 没有找到指定元素，返回负数，表示key应该插入到此位置以保证数组的有序性

binarySearch方法的使用

下面我们来看一下如何使用binarySearch方法：

int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int key = 6;
int index = Arrays.binarySearch(arr, key);
System.out.println("index:" + index); // 输出：index:5

上面的代码中，我们声明了一个有序的数组arr，然后查找其中的元素6，binarySearch方法返回了该元素的索引5。

接下来我们来看一个key不存在于数组中的例子：

int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int key = 20;
int index = Arrays.binarySearch(arr, key);
System.out.println("index:" + index); // 输出：index:-11

上面的代码中，我们查找不存在数组中的元素20，binarySearch方法返回了-11。这个返回值表示，如果要将元素20插入数组中，应该插入到第11个位置（从1开始），才能保证数组的有序性。

总结

binarySearch方法是一个非常高效的查找有序数组中的元素的方法。在使用时需要注意传入的数组必须是有序的。如果传入的数组是无序的，应首先使用sort方法对其进行排序。