二分查找又稱折半查找，它是一種效率較高的查找方法。
折半查找的算法思想是將數(shù)列按有序化(遞增或遞減)排列，查找過程中采用跳躍式方式查找，即先以有序數(shù)列的中點(diǎn)位置為比較對象，如果要找的元素值小 于該中點(diǎn)元素，則將待查序列縮小為左半部分，否則為右半部分。通過一次比較，將查找區(qū)間縮小一半。 折半查找是一種高效的查找方法。它可以明顯減少比較次數(shù)，提高查找效率。但是，折半查找的先決條件是查找表中的數(shù)據(jù)元素必須有序。
折半查找法的優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好;其缺點(diǎn)是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經(jīng)常變動而查找頻繁的有序列表。
二分算法步驟描述
① 首先確定整個(gè)查找區(qū)間的中間位置 mid = （ left + right ）/ 2
② 用待查關(guān)鍵字值與中間位置的關(guān)鍵字值進(jìn)行比較；
若相等，則查找成功
若大于，則在后（右）半個(gè)區(qū)域繼續(xù)進(jìn)行折半查找
若小于，則在前（左）半個(gè)區(qū)域繼續(xù)進(jìn)行折半查找
③ 對確定的縮小區(qū)域再按折半公式，重復(fù)上述步驟。
最后，得到結(jié)果：要么查找成功， 要么查找失敗。折半查找的存儲結(jié)構(gòu)采用一維數(shù)組存放。 折半查找算法舉例
對給定數(shù)列（有序）{ 3,5,11,17,21,23,28,30,32,50,64,78,81,95,101}，按折半查找算法，查找關(guān)鍵字值為81的數(shù)據(jù)元素。
二分查找算法討論：
優(yōu)點(diǎn)：ASL≤log2n，即每經(jīng)過一次比較,查找范圍就縮小一半。經(jīng)log2n 次計(jì)較就可以完成查找過程。
缺點(diǎn)：因要求有序，所以要求查找數(shù)列必須有序，而對所有數(shù)據(jù)元素按大小排序是非常費(fèi)時(shí)的操作。另外，順序存儲結(jié)構(gòu)的插入、刪除操作不便利。
考慮：能否通過一次比較拋棄更多的部分（即經(jīng)過一次比較，使查找范圍縮得更小），以達(dá)到提高效率的目的。……？
可以考慮把兩種方法（順序查找和折半查找）結(jié)合起來，即取順序查找簡單和折半查找高效之所長，來達(dá)到提高效率的目的？實(shí)際上這就是分塊查找的算法思想。
Java二分查找源碼
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
public class BinarySearch { /** * 二分查找算法 * * @param srcArray * 有序數(shù)組 * @param key * 查找元素 * @return key的數(shù)組下標(biāo)，沒找到返回-1 */ public static void main(String[] args) { int srcArray[] = { 3, 5, 11, 17, 21, 23, 28, 30, 32, 50, 64, 78, 81, 95, 101 }; System.out.println(binSearch(srcArray, 0, srcArray.length - 1, 81)); } // 二分查找遞歸實(shí)現(xiàn) public static int binSearch(int srcArray[], int start, int end, int key) { int mid = (end - start) / 2 + start; if (srcArray[mid] == key) { return mid; } if (start >= end) { return -1; } else if (key > srcArray[mid]) { return binSearch(srcArray, mid + 1, end, key); } else if (key < srcArray[mid]) { return binSearch(srcArray, start, mid - 1, key); } return -1; } // 二分查找普通循環(huán)實(shí)現(xiàn) public static int binSearch(int srcArray[], int key) { int mid = srcArray.length / 2; if (key == srcArray[mid]) { return mid; } int start = 0; int end = srcArray.length - 1; while (start <= end) { mid = (end - start) / 2 + start; if (key < srcArray[mid]) { end = mid - 1; } else if (key > srcArray[mid]) { start = mid + 1; } else { return mid; } } return -1; }} |
以上就是Java 二分查找算法的實(shí)現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于Java 二分查找算法的資料請關(guān)注服務(wù)器之家其它相關(guān)文章！
原文鏈接：https://www.open-open.com/code/view/1420709718703
