溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
一，二分法檢索算法介紹
二分法檢索（binary search）又稱折半檢索，二分法檢索的基本思想是設(shè)字典中的元素從小到大有序地存放在數(shù)組（array）中。是最常用的搜索算法之一，這主要是由于其搜索時間短。
二，二分法檢索算法思路
這種搜索使用分而治之方法，并且需要事先對數(shù)據(jù)集進行排序。
它將輸入集合分為相等的兩半，并且每次迭代都將目標元素與中間元素進行比較。
如果找到該元素，則搜索結(jié)束。否則，我們根據(jù)目標元素是小于還是大于中間元素，通過劃分并選擇適當?shù)臄?shù)組分區(qū)來繼續(xù)尋找元素。
這就是為什么對Binary Search有一個排序的集合很重要的原因。
當firstIndex（我們的指針）經(jīng)過lastIndex（最后一個元素）時，搜索將終止，這意味著我們已經(jīng)搜索了整個數(shù)組，并且該元素不存在。
有兩種方法可以實現(xiàn)此算法- 迭代和遞歸。
這里不應(yīng)該是關(guān)于時間和空間這兩個實現(xiàn)之間復(fù)雜的差異，雖然這不成立于所有語言。
三，二分法檢索算法代碼實現(xiàn)
迭代式
首先讓我們看一下迭代方法：
public class SearchAlgorithms {
/**
*迭代方法
* @param arr
* @param elementToSearch
* @return
*/
public static int binarySearch(int arr[], int elementToSearch) {
int firstIndex = 0;
int lastIndex = arr.length - 1;
// 終止條件(元素不存在)
while(firstIndex <= lastIndex) {
int middleIndex = (firstIndex + lastIndex) / 2;
// 如果中間元素是我們的目標元素，那么返回它的索引
if (arr[middleIndex] == elementToSearch) {
return middleIndex;
}
// 如果中間的元素比較小
// 將我們的指數(shù)指向中間+1，不考慮前半部分
else if (arr[middleIndex] < elementToSearch)
firstIndex = middleIndex + 1;
// 如果中間的元素更大
// 將我們的指數(shù)指向中間1，不考慮下半部分
else if (arr[middleIndex] > elementToSearch)
lastIndex = middleIndex - 1;
}
return -1;
}
/**
* 用于打印結(jié)果
* @param targetParameter
* @param index
*/
public static void print(int targetParameter, int index) {
if (index == -1){
System.out.println(targetParameter + " 未找到");
}
else {
System.out.println(targetParameter + " 搜索結(jié)果為: " + index);
}
}
//測試一下
public static void main(String[] args) {
int index = binarySearch(new int[]{89, 57, 91, 47, 95, 3, 27, 22, 67, 99}, 67);
print(67, index);
}
}
輸出：
遞歸的
現(xiàn)在讓我們看一下遞歸實現(xiàn)：
遞歸方法的區(qū)別在于，一旦獲得新分區(qū)，我們便會調(diào)用方法本身。在迭代方法中，每當確定新分區(qū)時，我們都會修改第一個和最后一個元素，并在同一循環(huán)中重復(fù)該過程。
這里的另一個區(qū)別是遞歸調(diào)用被推入方法調(diào)用堆棧，并且每個遞歸調(diào)用占用一個空間單位。
我們可以像這樣使用這種算法：
public class SearchAlgorithms {
/**
*遞歸方法
* @param arr
* @param elementToSearch
* @return
*/
public static int recursiveBinarySearch(int arr[], int firstElement, int lastElement, int elementToSearch) {
// 結(jié)束條件
if (lastElement >= firstElement) {
int mid = firstElement + (lastElement - firstElement) / 2;
// 如果中間元素是我們的目標元素，那么返回它的索引
if (arr[mid] == elementToSearch)
return mid;
// 如果中間元素大于目標元素
if (arr[mid] > elementToSearch)
return recursiveBinarySearch(arr, firstElement, mid - 1, elementToSearch);
return recursiveBinarySearch(arr, mid + 1, lastElement, elementToSearch);
}
return -1;
}
/**
* 用于打印結(jié)果
* @param targetParameter
* @param index
*/
public static void print(int targetParameter, int index) {
if (index == -1){
System.out.println(targetParameter + " 未找到");
}
else {
System.out.println(targetParameter + " 搜索結(jié)果為: " + index);
}
}
//測試一下
public static void main(String[] args) {
int index = recursiveBinarySearch(new int[]{3, 22, 27, 47, 57, 67, 89, 91, 95, 99}, 0, 10, 67);
print(67, index);
}
}
輸出：
四，以算法時間復(fù)雜度和空間復(fù)雜度總結(jié)算法。
時間復(fù)雜度
由于二進制搜索每次將其時間復(fù)雜度為O（log（N））時都會將數(shù)組分為兩半。此時間復(fù)雜度是線性搜索O（N）時間復(fù)雜度的顯著改進。
空間復(fù)雜度
此搜索僅需要一個空間單位即可存儲要搜索的元素。因此，其空間復(fù)雜度為O（1）。
如果二分法檢索是遞歸實現(xiàn)的，則需要將對該方法的調(diào)用存儲在堆棧中。在最壞的情況下，這可能需要O（log（N））空間。
它是大多數(shù)用于搜索的庫中最常用的搜索算法，二分法檢索樹也被許多存儲排序數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)所使用。
該Arrays.binarySearch方法中的Java API也實現(xiàn)了二進制搜索哦。
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機網(wǎng)站二維碼