Gruntle Software & Testing

Java中的二进制搜索算法--实现& 示例

通过 Stewart Tristian发布于 发布在 指南

本教程将解释二进制搜索和amp; 递归二进制搜索在Java及其算法，实现和Java二进制搜索代码示例：

Java中的二进制搜索是一种用于在集合中搜索目标值或键的技术。 它是一种使用 "分而治之 "技术来搜索键的技术。

应用二进制搜索的集合需要以升序排序来搜索一个键。

通常情况下，大多数编程语言都支持线性搜索、二进制搜索和哈希技术，用于搜索集合中的数据。 我们将在后续教程中学习哈希技术。

在Java中的二进制搜索

线性搜索是一种基本技术。 在这种技术中，数组被依次遍历，每个元素都与键进行比较，直到找到键或达到数组的末端。

线性搜索在实际应用中很少使用。 二进制搜索是最经常使用的技术，因为它比线性搜索快得多。

Java提供了三种方法来执行二进制搜索：

  1. 使用迭代方法
  2. 使用递归的方法
  3. 使用Arrays.binarySearch（）方法。

在本教程中，我们将实现并讨论所有这3种方法。

在Java中进行二进制搜索的算法

在二进制搜索方法中，集合被反复分成两半，根据关键元素是否小于或大于集合的中间元素，在集合的左半部分或右半部分进行搜索。

一个简单的二进制搜索算法如下：

  1. 计算出集合的中间元素。
  2. 将关键项目与中间元素进行比较。
  3. 如果键=中间元素，那么我们返回找到的键的中间索引位置。
  4. Else 如果key>mid元素，那么key位于集合的右半部分。 因此在集合的下半部分（右）重复步骤1到3。
  5. 因此，你需要在上半部分重复二进制搜索。

从以上步骤可以看出，在二进制搜索中，集合中的一半元素在第一次比较后就被忽略了。

请注意，同样的步骤顺序适用于迭代和递归二进制搜索。

让我们用一个例子来说明二进制搜索算法的情况。

例如，以下面这个有10个元素的排序数组为例。

让我们计算一下数组的中间位置。

中=0+9/2=4

#1）钥匙=21

首先，我们将比较键值和[mid]元素，我们发现mid的元素值=21。

因此，我们发现钥匙=[mid]。 因此，钥匙在数组的第4个位置被找到。

#2）钥匙=25

我们首先将键值与mid进行比较。 由于(21 <25)，我们将直接在数组的上半部分搜索键。

现在我们将再次找到阵列上半部分的中点。

中=4+9/2=6

在位置[mid]的值=25

现在我们将关键元素与中间元素进行比较。 所以（25==25），因此我们在[中间]=6的位置找到了钥匙。

因此，我们反复分割数组，通过比较关键元素和中间元素，决定在哪一半中搜索关键元素。 二进制搜索在时间和正确性方面更有效率，而且速度也快很多。

二进制搜索的实现 Java

利用上述算法，让我们用迭代法在Java中实现一个二进制搜索程序。 在这个程序中，我们取一个例子数组，对这个数组进行二进制搜索。 

 import java.util.*; class Main{ public static void main(String args[]){ int numArray[] = {5,10,15,20,25,30,35}; System.out.println("The input array: " + Arrays.toString(numArray)); //key to be searched int key = 20; System.out.println("/nKey to be searched=" + key); //set first to first index int first = 0; //set last to last elements in array int last=numArray.length-1; //计算 mid ofarray int mid = (first + last)/2; //while first and last do not overlap while( first <= last ){ //if the mid <key, then key to be searched is in the first half of array if ( numArray[mid] last ){ System.out.println("Element is not found!") ; } } }

输出：

输入阵列：[5，10，15，20，25，30，35］

要搜索的关键=20

在索引中发现元素：3

上面的程序显示了二进制搜索的迭代方法。 最初，声明一个数组，然后定义一个要搜索的键。

在计算出数组的中间元素后，将键与中间元素进行比较，然后根据键是小于还是大于键，分别在数组的下半部分或上半部分进行搜索。

Java中的递归二进制搜索

你也可以使用递归技术进行二进制搜索。 在这里，二进制搜索方法被递归调用，直到找到钥匙或整个列表被用完。

下面给出了实现递归二进制搜索的程序： 

 import java.util.*; class Main{ //二进制搜索的递归方法 public static int binary_Search(int intArray[], int low, int high, int key){ //如果数组是有序的，那么对数组进行二进制搜索 if (high>=low){ //计算中间 int mid = low + (high - low)/2; //如果 key =intArray[mid] return mid if (intArray[mid] == key){ return mid; } //如果intArray[mid]> key 那么 key 在左边if (intArray[mid]> key){ return binary_Search(intArray, low, mid-1, key);//recursively search for key }else //key is in right half of array { return binary_Search(intArray, mid+1, high, key);//recursively search for key } return -1; } public static void main(String args[] ){ //define array and key int intArray[] = {1,11,21,31,41,51,61,71,81,91}; System.out.println("InputList: " + Arrays.toString(intArray)); int key = 31; System.out.println("\nThe key to be searched:" + key); int high=intArray.length-1; //调用二进制搜索方法 int result = binary_Search(intArray,0,high,key); //打印结果 if (result == -1) System.out.println(" /nKey not found in given list!" ); else System.out.println(" /nKey is found at location: " +result + " in the list"); } }

输出：

输入列表：[1，11，21，31，41，51，61，71，81，91

要搜索的关键：

在列表中的位置找到钥匙：3

使用Arrays.binarySearch（）方法。

Java中的Arrays类提供了一个'binarySearch()'方法，对给定的Array进行二进制搜索。 该方法将数组和要搜索的键作为参数，并返回键在数组中的位置。 如果没有找到键，那么该方法返回-1。

下面的例子实现了Arrays.binarySearch（）方法。 

 import java.util.Arrays; class Main{ public static void main(String args[]){ //定义一个数组 intArray[] = {10,20,30,40,50,60,70,80,90}; System.out.println("The input Array : " + Arrays.toString(intArray)); //定义要搜索的键 int key = 50; System.out.println("\nThe key to be search: " + key); //在给定数组中调用 binarySearch 方法，搜索键 int result =Arrays.binarySearch(intArray,key); //打印返回结果 if (result <0) System.out.println("\nKey is not found in the array!"); else System.out.println("\nKey is found at index: "+result + " in the array."); } }

输出：

输入数组：[10, 20, 30, 40, 50, 60, 70, 80, 90] 。

要搜索的关键：50

键在数组中的索引：4处找到。

常见问题

问题#1）如何编写二进制搜索？

答案是： 二进制搜索通常是通过将数组分成两半来进行的。 如果要搜索的键大于中间元素，那么就通过进一步划分和搜索子数组来搜索数组的上半部分，直到找到键。

同样，如果键值小于中间元素，那么键值就在数组的下半部分进行搜索。

问题#2）二进制搜索用在哪里？

答案是： 二进制搜索主要用于搜索软件应用中的分类数据，特别是当内存空间紧凑和有限时。

问题#3）二进制搜索的大O是什么？

答案是： 二进制搜索的时间复杂度为O（logn），其中n为数组中的元素数。 二进制搜索的空间复杂度为O（1）。

问题#4）二进制搜索是递归吗？

答案是： 是的，因为二进制搜索是分而治之的策略的一个例子，它可以用递归来实现。 我们可以把数组分成两半，然后反复调用同一个方法来执行二进制搜索。

问题#5）为什么被称为二进制搜索？

答案是： 二进制搜索算法使用了一种分而治之的策略，重复地将数组切成两半或两部分。 因此，它被命名为二进制搜索。

总结

二进制搜索是Java中经常使用的搜索技术。 进行二进制搜索的要求是，数据应按升序排序。

二进制搜索可以用迭代或递归的方法来实现。 Java中的Arrays类也提供了'binarySearch'方法，在数组上执行二进制搜索。

在我们后续的教程中，我们将探索Java中的各种排序技术。

滚动到顶部