Java 中的二分查找(​​)

在 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 中是如何工作的：

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

在 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) );
}
}

输出：

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

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

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

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

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

我们可以看到，位置打印为-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);
}
}

输出：

上面的程序中，首先创建了一个数组，并声明了要查找的元素。使用binarySearch()方法，可以找出关键元素的位置。  假设没有找到该元素，则会打印一条消息“Sorry !!!Can't find the element”。

结论

binarySearch() 是一种 Java 方法，可帮助使用二分搜索算法在数组中的多个可用元素中查找特定的关键元素。本文档详细解释了此方法的工作原理和示例。

推荐文章

这是 Java 中 BinarySearch() 的指南。在这里，我们讨论 BinarySearch() 方法在 Java 中的工作原理以及代码实现的示例。您还可以阅读我们其他推荐的文章以了解更多信息 –

1. JavaScript 数学函数
2. Java 中的布局
3. Java 编译器
4. Java 中的合并排序

以上是Java 中的二分查找(​​)的详细内容。更多信息请关注PHP中文网其他相关文章！