Java 中的二分查找()-java教程-PHP中文网

在 Java 中，binarySearch() 是一种帮助使用二分搜索算法从多个元素中搜索特定键元素的方法。为了执行此操作，元素必须按升序排序。如果没有排序，可以使用Arrays.sort(arr)方法进行排序。否则，结果被认为是未定义的。与线性搜索相比，二分搜索被认为更快。因此，二分查找的时间复杂度为 O(log n)。此外，binarySearch() 方法可以从 java.util.Arrays 包中实例化。有关 binarySearch() 方法的更多详细信息将在以下部分中讨论。

语法：

开始您的免费软件开发课程

网络开发、编程语言、软件测试及其他

public static int binarySearch(Object[] a, Object key)

登录后复制

这里参数a和key分别是要查找的数组和要查找的值。

binarySearch() 方法返回正在搜索的关键元素的索引。在未找到关键元素的情况下，将返回本来要插入的关键元素的插入点。如果搜索的关键元素与数组中的其他元素不可比较，则会抛出称为 ClassCastException 的异常。

BinarySearch() 方法在 Java 中如何工作？

让我们看看这个方法在 Java 中是如何工作的：

假设k是要搜索的关键元素。将 k 与数组的中间元素进行比较。
如果 k 与中间位置的元素匹配，则必须返回中间索引。
否则，如果k比中间位置的元素高，那么k只能在中间元素的右侧找到。
否则可以在中间元素的左侧找到。

在 Java 中实现 BinarySearch() 的示例

下面是一些使用 BinarySearch() 方法的程序示例。

示例#1

代码：

import java.util.Arrays;
public class BinarySearchExample
{
public static void main(String[] args)
{
//create a byte array
byte ba[] = {05, 10, 15, 20, 25, 30};
//create a character array
char ca[] = {'a', 'n', 's', 'p', 'v', 'i', 'd'};
//create an integer array
int ia[] = { 10, 20, 15, 22, 35};
//create a double array
double da[] = {10.1 , 15.34 , 22.25, 13.5};
//create a float array
float fa[] = {13.2f, 25.1f , 22.2f , 43.5f };
//sort all the arrays that created above
Arrays.sort(ba);
Arrays.sort(ca);
Arrays.sort(ia);
Arrays.sort(da);
Arrays.sort(fa);
//enter the key elements that has to be searched in the array
byte bKey = 15;
char cKey = 'i';
int iKey = 22;
double dKey = 15.34;
float fKey = 22.2f;
System.out.println("Element "+ bKey + " is found at the position of " + Arrays.binarySearch(ba,bKey) );
System.out.println("Element "+ cKey + " is found at the position of " + Arrays.binarySearch(ca,cKey) );
System.out.println("Element "+ iKey + " is found at the position of " + Arrays.binarySearch(ia,iKey) );
System.out.println("Element "+ dKey + " is found at the position of " + Arrays.binarySearch(da,dKey) );
System.out.println("Element "+ fKey + " is found at the position of " + Arrays.binarySearch(fa,fKey) );
}
}

登录后复制

输出：

Java 中的二分查找()

上述程序中使用 Arrays 对数组进行排序后，创建了字符、整数、浮点、双精度和字节等不同类型的数组。Sort() 方法中声明了需要在数组中搜索的元素。然后使用 Arrays.binarySearch() 方法打印搜索到的元素的索引。

假设给定一个数组中不存在的关键元素；输出是什么？

为了找到这一点，让我们更改关键元素的代码，如下所示。

字节 bKey = 15;
char cKey = ‘i’;
int iKey = 89;
双 dKey = 15.34;
浮动 fKey = 22.2f;

也就是说，iKey=89 不存在于数组中，那么输出将显示如下。

Java 中的二分查找()

我们可以看到，位置打印为-6。这是因为，如果搜索某个元素但未找到，则如果该元素存在，则将返回索引的负值。即，int ia[] = { 10, 20, 15, 22, 35} 是给定的数组。如果存在 89，则数组将为 int ia[] = { 10, 20, 15, 22, 35, 89};

可以清楚地看到索引将为 6。由于原始数组中不存在该索引，因此在上面的输出中返回了该特定索引的负值。

示例#2

二分查找也可以借助递归来完成，如下所示。

代码：

//sample class
class BinarySearchExample{
public static int binarySearch(int a[], int f, int l, int k){
//if last element is greater than or equal to first element
if (l>=f)
{
//find the mid
int m = f + (l - f)/2;
//if the key element that is searching is found in middle position, return mid position
if (a[m] == k)
{
return m;
}
//if key element is less than element in middle position, search the left <u>subarray</u>
if (a[m] > k){
return binarySearch(a, f, m-1, k);
}
//if key element is greater than the element in middle position, search the right <u>subarray</u>
else{
return binarySearch(a, m+1, l, k);
}
}
return -1;
}
public static void main(String args[]){
//initialise the array
int a[] = {34,45,54,68,79};
int k = 68;
int l = a.length-1;
//store the position in variable res
int res = binarySearch(a,0,l,k);
if (res == -1)
System.out.println("Sorry!! Can't find the element....!");
else
System.out.println("Element is found at the position: "+res);
}
}

登录后复制

输出：

Java 中的二分查找()