本教程将解释二进制搜索和amp; 递归二进制搜索在Java及其算法,实现和Java二进制搜索代码示例:
Java中的二进制搜索是一种用于在集合中搜索目标值或键的技术。 它是一种使用 "分而治之 "技术来搜索键的技术。
应用二进制搜索的集合需要以升序排序来搜索一个键。
通常情况下,大多数编程语言都支持线性搜索、二进制搜索和哈希技术,用于搜索集合中的数据。 我们将在后续教程中学习哈希技术。
在Java中的二进制搜索
线性搜索是一种基本技术。 在这种技术中,数组被依次遍历,每个元素都与键进行比较,直到找到键或达到数组的末端。
线性搜索在实际应用中很少使用。 二进制搜索是最经常使用的技术,因为它比线性搜索快得多。
Java提供了三种方法来执行二进制搜索:
- 使用迭代方法
- 使用递归的方法
- 使用Arrays.binarySearch()方法。
在本教程中,我们将实现并讨论所有这3种方法。
在Java中进行二进制搜索的算法
在二进制搜索方法中,集合被反复分成两半,根据关键元素是否小于或大于集合的中间元素,在集合的左半部分或右半部分进行搜索。
一个简单的二进制搜索算法如下:
- 计算出集合的中间元素。
- 将关键项目与中间元素进行比较。
- 如果键=中间元素,那么我们返回找到的键的中间索引位置。
- Else 如果key>mid元素,那么key位于集合的右半部分。 因此在集合的下半部分(右)重复步骤1到3。
- 因此,你需要在上半部分重复二进制搜索。
从以上步骤可以看出,在二进制搜索中,集合中的一半元素在第一次比较后就被忽略了。
请注意,同样的步骤顺序适用于迭代和递归二进制搜索。
让我们用一个例子来说明二进制搜索算法的情况。
例如,以下面这个有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中的各种排序技术。