Java实现二分查找法

约定不等于承诺〃 2023-10-04 09:09 26阅读 0赞

本教程将介绍Java中的二分查找和递归二分查找算法。

Java中的二分查找是一种用于在集合中查找目标值或键的技术。它是一种使用“分而治之”技术查找关键字的技术。

应用二分查找来查找关键字的集合需要按升序排序。

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

### Java中的二分查找 ###

线性查找是一项基本技术。在此技术中，顺序遍历数组，并将每个元素与键进行比较，直到找到键或到达数组的末尾为止。

线性查找在实际应用中很少使用。二分查找是最常用的技术，因为它比线性查找快得多。

**Java提供了三种实现二分查找的方式：**

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

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

#### Java中的二分查找算法 ####

在二分查找方法中，将集合重复地分成两半，并根据关键字是小于还是大于集合的中间元素来在集合的左半部分或右半部分中搜索关键元素。

**一种简单的二分查找算法如下：**

1.  计算集合的中间元素。
2.  将关键项与中间元素进行比较。
3.  如果key = middle元素，则返回找到的键的中间索引位置。
4.  否则，如果键>中间元素，则键位于集合的右半部分。因此，在集合的下半部分（右）重复步骤1到3。
5.  其他键<中间元素，则键在集合的上半部分。因此，您需要在上半部分重复二分查找。

从上述步骤中可以看到，在二分查找中，在第一次比较之后，集合中的一半元素将被忽略。

注意，相同的步骤顺序适用于迭代和递归二分查找。

让我们使用一个例子来说明二分查找算法。

**例如，采用10个元素的以下排序数组。**

[![10个元素的排序数组][10]][10_10]

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

中= 0 + 9/2 = 4

[![数组的中间位置][b2514b0bcf26c2da2369534eadbf0f2e.png]][b2514b0bcf26c2da2369534eadbf0f2e.png 1]

**＃1）键= 21**

首先，我们将键值与\[mid\]元素进行比较，发现在mid = 21处的元素值。

[![键= 21][21]][21_21]

因此，我们发现密钥= \[mid\]。因此，可以在数组中的位置4找到密钥。

**＃2）键= 25**

[![键= 25][25]][25_25]

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

[![在数组的上半部分搜索键。][857aca351685fd4d5dfa11a6729bdff9.png]][857aca351685fd4d5dfa11a6729bdff9.png 1]

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

中= 4 + 9/2 = 6

位置\[mid\]处的值= 25

[![位置\[中\]的值= 25][25 1]][25_25 1]

现在，我们将键元素与中间元素进行比较。因此（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 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;
    		// calculate mid of the array
    		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] < key) {
    				first = mid + 1;
    			} else if (numArray[mid] == key) {
    				// if key = element at mid, then print the location
    				System.out.println("Element is found at index: " + mid);
    				break;
    			} else {
    				// the key is to be searched in the second half of the array
    				last = mid - 1;
    			}
    			mid = (first + last) / 2;
    		}
    		// if first and last overlap, then key is not present in the array
    		if (first > last) {
    			System.out.println("Element is not found!");
    		}
    	}
    }

**输出：**

输入数组：\[5、10、15、20、25、30、35\]  
要搜索的键= 20  
在索引：3处找到元素

[![输出-二进制搜索实现Java][-_Java]][-_Java_-_Java]

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

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

#### Java中的递归二分查找 ####

您还可以使用递归技术执行二分查找。在此，递归调用二分查找方法，直到找到关键字或整个列表用尽。

**下面给出了实现递归二分查找的程序：**

package BinarySearch;
    
    import java.util.*;
    
    class BinarySearchRecursive {
    	// recursive method for binary search
    	public static int binary_Search(int intArray[], int low, int high, int key) {
    		// if array is in order then perform binary search on the array
    		if (high >= low) {
    			// calculate mid
    			int mid = low + (high - low) / 2;
    			// if key =intArray[mid] return mid
    			if (intArray[mid] == key) {
    				return mid;
    			}
    			// if intArray[mid] > key then key is in left half of array
    			if (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 key
    		int 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 method
    		int result = binary_Search(intArray, 0, high, key);
    		// print the result
    		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

[![输出-Java中的递归二进制搜索][-Java]][-Java_-Java]

#### 使用Arrays.binarySearch（）方法。 ####

Java中的Arrays类提供了一种'binarySearch（）'方法，该方法在给定的Array上执行二分查找。此方法将数组和要搜索的键作为参数，并返回键在数组中的位置。如果找不到该键，则该方法返回-1。

**下面的示例实现Arrays.binarySearch（）方法。**

package BinarySearch;
    
    import java.util.Arrays;
    
    class BinarySearchArrays {
    	public static void main(String args[]) {
    		// define an array
    		int intArray[] = { 10, 20, 30, 40, 50, 60, 70, 80, 90 };
    		System.out.println("The input Array : " + Arrays.toString(intArray));
    		// define the key to be searched
    		int key = 50;
    		System.out.println("\nThe key to be searched:" + key);
    		// call binarySearch method on the given array with key to be searched
    		int result = Arrays.binarySearch(intArray, key);
    		// print the return result
    		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.");
    	}
    }

**输出：**

输入Array：\[10，20，30，40，50，60，70，80，90\]  
要搜索的键：50  
键位于数组的索引：4处。

[![输出-使用Arrays.binarySearch（）方法。][-_Arrays.binarySearch]][-_Arrays.binarySearch_-_Arrays.binarySearch]

#### 经常问的问题 ####

**问＃1）您如何编写二分查找？**

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

同样，如果键小于中间元素，则在数组的下半部分搜索键。

**问＃2）二分查找在哪里使用？**

**答：**二分查找主要用于在软件应用程序中搜索排序的数据，尤其是在存储空间紧凑且有限的情况下。

**Q＃3）二分查找的最大作用是什么？**

**答：**二分查找的时间复杂度为O（logn），其中n是数组中元素的数量。二分查找的空间复杂度为O（1）。

**问＃4）二分查找是否递归？**

**答：可以**。由于二分查找是分而治之策略的一个示例，因此可以使用递归来实现。我们可以将数组分成两半，然后调用相同的方法来一次又一次地执行二分查找。

**问＃5）为什么称其为二分查找？**

**答：**二分查找算法使用分而治之的策略，该策略反复将数组切成两半或两部分。因此，它被称为二分查找。

### 结论 ###

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

可以使用迭代或递归方法来实现二分查找。Java中的Arrays类还提供了'binarySearch'方法，该方法对Array执行二分查找。

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

[10]: https://img-blog.csdnimg.cn/img_convert/35abd453ccb338cba7f6b13f32ca1395.png
[10_10]: https://www.softwaretestinghelp.com/wp-content/qa/uploads/2020/03/1-5.png
[b2514b0bcf26c2da2369534eadbf0f2e.png]: https://img-blog.csdnimg.cn/img_convert/b2514b0bcf26c2da2369534eadbf0f2e.png
[b2514b0bcf26c2da2369534eadbf0f2e.png 1]: https://www.softwaretestinghelp.com/wp-content/qa/uploads/2020/03/2-4.png
[21]: https://img-blog.csdnimg.cn/img_convert/53d92c3286085ee1c8120aaafba92f0b.png
[21_21]: https://www.softwaretestinghelp.com/wp-content/qa/uploads/2020/03/3-4.png
[25]: https://img-blog.csdnimg.cn/img_convert/377a0490c011450c73a6e0809434d0ad.png
[25_25]: https://www.softwaretestinghelp.com/wp-content/qa/uploads/2020/03/4-3.png
[857aca351685fd4d5dfa11a6729bdff9.png]: https://img-blog.csdnimg.cn/img_convert/857aca351685fd4d5dfa11a6729bdff9.png
[857aca351685fd4d5dfa11a6729bdff9.png 1]: https://www.softwaretestinghelp.com/wp-content/qa/uploads/2020/03/5-3.png
[25 1]: https://img-blog.csdnimg.cn/img_convert/a5544ff95783d1b76b8cfa1057311ce8.png
[25_25 1]: https://www.softwaretestinghelp.com/wp-content/qa/uploads/2020/03/6-2.png
[-_Java]: https://img-blog.csdnimg.cn/img_convert/15f35bce7a81bfd0ced60df4e6f4e5b0.png
[-_Java_-_Java]: https://www.softwaretestinghelp.com/wp-content/qa/uploads/2020/03/7-2.png
[-Java]: https://img-blog.csdnimg.cn/img_convert/3689a4426496691e8d39b22e65f407db.png
[-Java_-Java]: https://www.softwaretestinghelp.com/wp-content/qa/uploads/2020/03/8-1.png
[-_Arrays.binarySearch]: https://img-blog.csdnimg.cn/img_convert/91946370c191bbb575c41df400ab3fa4.png
[-_Arrays.binarySearch_-_Arrays.binarySearch]: https://www.softwaretestinghelp.com/wp-content/qa/uploads/2020/03/9-1.png