Java二分查找算法實例詳解
在本文中，我們將介紹二進制搜索相對於簡單線性搜索的優勢，並介紹它在 Java 中的實現。
1. 需要有效的搜索
假設我們在wine-selling業務和數以百萬計的買傢每天都訪問我們的應用程序。
通過我們的應用程序,客戶可以過濾掉物品價格低於n美元,從搜索結果中選擇一個瓶子,並將它們添加到購物車。我們有成千上萬的用戶尋求葡萄酒價格限制每一秒。需要快速的結果。
後端,我們的算法運行的線性搜索整個列表葡萄酒比較價格限制輸入的客戶提供的價格每一個酒瓶在列表中。
然後,它返回物品的價格小於或等於價格限制。這個線性搜索時間復雜度為O (n)。
這意味著我們系統中的酒瓶數量越多，所需的時間就越多。搜索時間與引入的新項目的數量成正比。
如果我們開始按排序順序保存項目並使用二進制搜索搜索項目，我們可以實現O(log n)的復雜度。
對於二分搜索，搜索結果所花費的時間自然會隨著數據集的大小而增加，但不會成比例地增加。
2. 二分查找
簡單來說，算法將鍵值與數組的中間元素進行比較;如果它們不相等，則刪除不能包含密鑰的一半，並繼續搜索剩餘的一半，直到成功。
請記住 – 這裡的關鍵方面是數組已經排序。
如果搜索以剩餘的一半為空而結束，則該鍵不在數組中。
(1)迭代實現
public int runBinarySearchIteratively(
int[] sortedArray, int key, int low, int high) {
int index = Integer.MAX_VALUE;
while (low <= high) {
int mid = low + ((high - low) / 2);
if (sortedArray[mid] < key) {
low = mid + 1;
} else if (sortedArray[mid] > key) {
high = mid - 1;
} else if (sortedArray[mid] == key) {
index = mid;
break;
}
}
return index;
}
runBinarySearchIteratively方法將sortedArray、key和 sortedArray 的低索引和高索引作為參數。當方法第一次運行時， sortedArray的第一個索引low為 0，而sortedArray的最後一個索引high等於其長度 – 1。
中間是sortedArray的中間索引。現在算法運行一個while循環，將鍵與sortedArray的中間索引的數組值進行比較。
註意中間索引是如何生成的(int mid = low + ((high – low) / 2)。這是為瞭適應非常大的數組。如果中間索引是通過獲取中間索引(int mid = (low + high) / 2) ，包含 2 30 個或更多元素的數組可能會發生溢出，因為low + high的總和很容易超過最大正int值。
(2)遞歸實現
現在，讓我們看看一個簡單的遞歸實現：
public int runBinarySearchRecursively(
int[] sortedArray, int key, int low, int high) {
int middle = low + ((high - low) / 2);
if (high < low) {
return -1;
}
if (key == sortedArray[middle]) {
return middle;
} else if (key < sortedArray[middle]) {
return runBinarySearchRecursively(
sortedArray, key, low, middle - 1);
} else {
return runBinarySearchRecursively(
sortedArray, key, middle + 1, high);
}
}
runBinarySearchRecursively方法接受sortedArray、鍵、sortedArray的低索引和高索引。
(3)使用數組。二進制搜索()
int index = Arrays.binarySearch(sortedArray, key);
將在整數數組中搜索的 sortedArray和int key作為參數傳遞給Java Arrays類的binarySearch方法。
(4)使用集合。二進制搜索()
int index = Collections.binarySearch(sortedList, key);
sortedList &整數鍵,搜索列表中的整數對象,作為參數傳遞到binarySearch Java集合類的方法。
(5)性能
是否使用遞歸迭代的方法編寫的算法主要是一個個人喜好問題。但仍有一些觀點我們應該意識到:
1)慢遞歸可以維護一個堆棧的開銷和通常要占用更多的記憶空間
2)遞歸不是stack-friendly。它可能導致StackOverflowException當處理大數據集
3)遞歸添加清晰的代碼,使其較短的迭代方法相比
理想情況下,一個二叉搜索將執行更少數量的比較與一個線性搜索大的n, n為較小的值,值的線性搜索可以執行比二進制搜索。
每個人都應該知道這個分析是理論和可能取決於上下文。
此外，二分搜索算法需要一個排序的數據集，它也有它的成本。如果我們使用歸並排序算法對數據進行排序，則會在我們的代碼中增加n log n的額外復雜度。
知識點擴展：
二分算法步驟描述
① 首先確定整個查找區間的中間位置 mid = （ left + right ）/ 2
② 用待查關鍵字值與中間位置的關鍵字值進行比較；
若相等，則查找成功
若大於，則在後（右）半個區域繼續進行折半查找
若小於，則在前（左）半個區域繼續進行折半查找
③ 對確定的縮小區域再按折半公式，重復上述步驟。
最後，得到結果：要麼查找成功， 要麼查找失敗。折半查找的存儲結構采用一維數組存放。 折半查找算法舉例
對給定數列（有序）{ 3,5,11,17,21,23,28,30,32,50,64,78,81,95,101}，按折半查找算法，查找關鍵字值為81的數據元素。
到此這篇關於Java二分查找算法實例詳解的文章就介紹到這瞭,更多相關Java二分查找算法淺析內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！