本教程介绍Java的二分搜索和递归二分搜索算法。
Java二分查找是一种用于在集合中搜索目标值或键的技术。 是使用“分割统治”技术寻找关键词的技术。
应用二分查找搜索关键字的集合必须按升序排序。
大多数编程语言通常支持线性搜索、二分搜索和mydds技术来搜索集合中的数据。 您将在以下教程中学习mydds。
Java的二分搜索线性搜索是基本技术。 此方法按顺序遍历数组，并将每个元素与键进行比较，直到找到键或到达数组末尾。
线性检索在实用中很少使用。 二分搜索比线性搜索快得多，所以是最常用的技术。
Java提供了三种实现二分查找的方式：
使用迭代方法使用递归方法使用Arrays.binarySearch ()方法。在本教程中，我们将实现和讨论所有这三种方法。
Java二分搜索算法是一种二分搜索方法，将集合重复分成两半，根据关键字是小于还是大于集合的中间元素，在集合的左半部分或右半部分搜索关键元素。
一种简单的二分查找算法如下：
计算集合的中间元素。 比较关键项目和中间元素。 如果key=middle元素，则返回找到的键的中间索引位置。 否则，对于键的中间元素，键位于集合的右半部分。 因此，在集合的下半部分(右)重复步骤1到3。 对于其他键的中间元素，键位于集合的上半部分。 因此，需要在上半部分重复二分搜索。 从上面的步骤可以看出，二分搜索在第一次比较后会忽略集合中的一半元素。
请注意，相同的步骤适用于迭代和递归二分搜索。
用一个例子来说明二分搜索算法吧。
例如，采用10个元素的以下排序数组。
让我们计算数组的中间位置。
中=0 9/2=4
1）键= 21
首先，将关键值与[mid]元素进行比较，找到mid=21的元素值。
因此，发现密钥=[mid]。 因此，可以在数组中的位置4找到键。
2）键= 25
首先比较键值和中位数。 21因为25，所以直接在数组的上半部分搜索键。
然后，再次找到阵列上半部分的中央部分。
中=4 9/2=6
位置[mid]的值=25
现在，比较关键元素和中间元素。 因此，25==25，我们在位置[mid]=6找到了密钥。
因此，通过反复分割数组，比较关键要素和中间要素，决定按哪个一半搜索关键要素。 在时间和准确性方面，二进制搜索效率更高，速度也快得多。
基于Java的二分搜索
">使用上述算法，让我们使用迭代方法在Java中实现二分查找程序。在此程序中，我们以一个示例数组为例，并对该数组执行二分查找。 package BinarySearch;import java.util.*;class BinarySearchIterative {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 searchedint key = 20;System.out.println("nKey to be searched=" + key);// set first to first indexint first = 0;// set last to last elements in arrayint last = numArray.length - 1;// calculate mid of the arrayint mid = (first + last) / 2;// while first and last do not overlapwhile (first <= last) {// if the mid < key, then key to be searched is in the first half of arrayif (numArray[mid] < key) {first = mid + 1;} else if (numArray[mid] == key) {// if key = element at mid, then print the locationSystem.out.println("Element is found at index: " + mid);break;} else {// the key is to be searched in the second half of the arraylast = mid - 1;}mid = (first + last) / 2;}// if first and last overlap, then key is not present in the arrayif (first > last) {System.out.println("Element is not found!");}}}
输出：
输入数组：[5、10、15、20、25、30、35]
要搜索的键= 20
在索引：3处找到元素
上面的程序显示了二进制搜索的迭代方法。最初，声明一个数组，然后定义要搜索的键。
在计算数组的中位数之后，将键与中位数元素进行比较。然后根据键是小于还是大于键，分别在数组的下半部分或上半部分中搜索该键。
Java中的递归二分查找您还可以使用递归技术执行二分查找。在此，递归调用二分查找方法，直到找到关键字或整个列表用尽。
下面给出了实现递归二分查找的程序：
package BinarySearch;import java.util.*;class BinarySearchRecursive {// recursive method for binary searchpublic static int binary_Search(int intArray[], int low, int high, int key) {// if array is in order then perform binary search on the arrayif (high >= low) {// calculate midint mid = low + (high - low) / 2;// if key =intArray[mid] return midif (intArray[mid] == key) {return mid;}// if intArray[mid] > key then key is in left half of arrayif (intArray[mid] > key) {return binary_Search(intArray, low, mid - 1, key);// recursively search for key} else // key is in right half of the array{return binary_Search(intArray, mid + 1, high, key);// recursively search for key}}return -1;}public static void main(String args[]) {// define array and keyint intArray[] = { 1, 11, 21, 31, 41, 51, 61, 71, 81, 91 };System.out.println("Input List: " + Arrays.toString(intArray));int key = 31;System.out.println("nThe key to be searched:" + key);int high = intArray.length - 1;// call binary search methodint result = binary_Search(intArray, 0, high, key);// print the resultif (result == -1)System.out.println("nKey not found in given list!");elseSystem.out.println("nKey is found at location: " + result + " in the list");}}输出：
输入列表：[1，11，21，31，41，51，61，71，81，91
要搜索的密钥：
密钥位于列表中的位置3
Java中的Arrays类提供了一种'binarySearch（）'方法，该方法在给定的Array上执行二分查找。此方法将数组和要搜索的键作为参数，并返回键在数组中的位置。如果找不到该键，则该方法返回-1。
下面的示例实现Arrays.binarySearch（）方法。
package BinarySearch;import java.util.Arrays;class BinarySearchArrays {public static void main(String args[]) {// define an arrayint intArray[] = { 10, 20, 30, 40, 50, 60, 70, 80, 90 };System.out.println("The input Array : " + Arrays.toString(intArray));// define the key to be searchedint key = 50;System.out.println("nThe key to be searched:" + key);// call binarySearch method on the given array with key to be searchedint result = Arrays.binarySearch(intArray, key);// print the return resultif (result < 0)System.out.println("nKey is not found in the array!");elseSystem.out.println("nKey is found at index: " + result + " in the array.");}}输出：
输入Array：[10，20，30，40，50，60，70，80，90]
要搜索的键：50
键位于数组的索引：4处。
问＃1）您如何编写二分查找？
答：二分查找通常是通过将数组分成两半来执行的。如果要搜索的键大于中间元素，则通过进一步划分和搜索子数组直到找到键来搜索数组的上半部分。
同样，如果键小于中间元素，则在数组的下半部分搜索键。
问＃2）二分查找在哪里使用？
答：二分查找主要用于在软件应用程序中搜索排序的数据，尤其是在存储空间紧凑且有限的情况下。
Q＃3）二分查找的最大作用是什么？
答：二分查找的时间复杂度为O（logn），其中n是数组中元素的数量。二分查找的空间复杂度为O（1）。
问＃4）二分查找是否递归？
答：可以。由于二分查找是分而治之策略的一个示例，因此可以使用递归来实现。我们可以将数组分成两半，然后调用相同的方法来一次又一次地执行二分查找。
问＃5）为什么称其为二分查找？
答：二分查找算法使用分而治之的策略，该策略反复将数组切成两半或两部分。因此，它被称为二分查找。
结论二分查找是Java中经常使用的搜索技术。执行二分查找的要求是，数据应按升序排序。
可以使用迭代或递归方法来实现二分查找。Java中的Arrays类还提供了'binarySearch'方法，该方法对Array执行二分查找。
在后续的教程中，我们将探讨Java中的各种排序技术。