【无标题】

2023-12-18 19:27:07

Arrays工具类二分查找方法binarySearch方法详解

  • 基础知识

该方法的一般形式是public static <T> int binarySearch(T[] a, T key),对于基本类型,都有相应的重载方法,如针对int类型有binarySearch(int[] a, int key)等。

该方法的原理是使用二分查找算法在指定的数组中搜索指定的值。在调用此方法之前,必须对数组进行排序(如通过sort(double[])方法),也即查找前数据必须是有序的。如果没有排序,则结果无意义。如果数组包含多个具有指定值的元素,则无法保证会找到哪一个。因此,调用本方法要保证源数组是有序的,且内部的元素是唯一的。

实际上,binarySearch方法可以对任意对象的数组进行排序,只需在调用本方法时实例化一个比较器Comparator即可,方法如下:

public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)
  • 返回值详解

该方法返回值为:

第一种情况:如果要搜索的值包含在数组中,则返回搜索键的索引值(是一个int值);

第二种情况:如果数值中找不到要查找的值(也即key),则返回值为:(-(插入点)- 1)。

插入点被定义为将键插入数组中的点:第一个大于键的元素的索引,或者如果数组中的所有元素都小于指定的键,则为a.length。返回负值的原因是要保证,如果能找到要查找的值时,返回值将大于等于0。

所以返回值有以下4种情况:

  1. 如果数组中所有值都大于要查找的值,那么将返回-1
  2. 如果要查找的值在数组中存在,则返回其索引
  3. 如果要查找的值不在数组中,但其值的大小在数组的范围内,则返回(-(插入点)- 1)
  4. 如果要查找的值大于数组中所有值,则返回(-(a.length)-1)

例如:

int[] arr = {10, 20, 30, 40, 50};
System.out.println(Arrays.binarySearch(arr, 50));
System.out.println(Arrays.binarySearch(arr, 15));

运行结果为:

4

-2

原理如图:

文章来源:https://blog.csdn.net/weixin_50083448/article/details/135065782
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。