Java 中的線性搜索一直是在數組中查找元素的首選方法。它按順序搜索數組的每個元素並且非常容易實現。但是，當所討論的數組包含數万個元素時，線性搜索的缺點就很明顯了。在這種情況下，二進制搜索實現的“分而治之”方法效率更高，對於考慮時間和空間複雜性的程序員來說更可取。
![Java 中的二進制搜索：遞歸、迭代和 Java 集合 - 1]()
二進制搜索
在二進制搜索中，一個數組被重複分成兩半，直到找到鍵（正在搜索的元素）。該劃分是虛擬的，即保持數據的完整性。每次迭代，都會關注數組的中間值。如果該值等於我們要查找的鍵，則循環或遞歸函數終止。否則，它將繼續循環。如果中間值大於鍵，則函數將關注數組的前半部分，反之亦然。重複此過程，直到找到鍵或遍歷整個數組。
線性搜索和二分搜索之間的區別
| 線性搜索 | 二進制搜索 |
|---|---|
| 順序搜索數組 | 將數組分成兩半，直到找到值 |
| 適用於任何陣列 | 僅適用於排序數組 |
| 複雜度為 O(N) | 複雜度為 O(log2N) |
| 可以處理排序和未排序的數組 | 只能在排序數組上實現。 |
| 實施起來不那麼複雜 | 實施起來更複雜 |
二進制搜索算法
下面給出二分查找的算法。- 確定數組的第一個和最後一個點。這些點將在每次迭代時根據數組和正在搜索的鍵進行調整。
- 遍歷數組並比較當前第一個點和最後一個點之間的中間值。在第一次迭代中，第一個和最後一個變量將與數組中的實際變量相同。
- 如果鍵大於中間值，則該值的索引將存儲在新的“First”變量中。
- 如果鍵小於中間值，則該值的索引將存儲在“最後”變量中。
- 重複此條件，直到兩個條件之一變為真：
- 鑰匙找到了。
- 整個數組已經迭代。
迭代二進制搜索
下面給出了使用迭代方法進行二分查找的代碼。
import java.util.Scanner;
public class IterativeBinarySearch {
public static void main(String[] args) {
int arr[] = {1,3,6,8,10};
System.out.println("Enter Number to Search For: ");
Scanner input = new Scanner (System.in);
int num = input.nextInt();
int result = BinarySearchIterative(arr,num);
if(result!=-1)
System.out.println("Value Found at Index #" + result);
else
System.out.println("Value Not Found");
}
public static int BinarySearchIterative(int[] arr, int num){
//Representing the Start and End Index After Division of Array
int start = 0;
int end = arr.length;
//Loop to Iterate Through the Array
for(int i = 0; iarr[n]){
start = n;
}
//If number to search for is greater than the arr value at index 'n'
else{
end = n;
}
}
//If number isn't found, return -1
return -1;
}
}
遞歸二分查找
下面給出了使用遞歸的二進制代碼。
import java.util.Scanner;
public class RecursiveBinarySearch {
public static void main(String[] args) {
int arr[] = {1,3,6,8,10};
System.out.println("Enter Number to Search For: ");
Scanner input = new Scanner (System.in);
int num = input.nextInt();
int result = BinarySearchRecursive(arr,0,arr.length-1,num);
if(result!=-1)
System.out.println("Value Found at Index #" + result);
else
System.out.println("Value Not Found");
}
public static int BinarySearchRecursive(int arr[], int a, int b, int num){
//Base Case to Exit the Recursive Function
if (b < 1) {
return -1;
}
int n = a + (b=1)/2;
//If number is found at mean index of start and end
if(arr[n]==num)
return n;
//If number to search for is greater than the arr value at index 'n'
else if(arr[n]>num)
return BinarySearchRecursive(arr,a,n-1,num);
//If number to search for is greater than the arr value at index 'n'
else
return BinarySearchRecursive(arr,n+1,b,num);
}
}
GO TO FULL VERSION