作者:nnngu
GitHub:https://github.com/nnngu
博客園:http://www.cnblogs.com/nnngu
簡(jiǎn)書:http://www.reibang.com/users/1df20d76ea5c
知乎:https://www.zhihu.com/people/nnngu/posts
二分查找屬于順序表查找伟叛,二分查找也稱為折半查找。二分查找的時(shí)間復(fù)雜度為O(log2n)
1脐嫂、二分查找的定義
什么是二分查找呢统刮?二分查找的基本思想是:在有序表中紊遵,取中間元素作為比較對(duì)象,若給定值與中間元素相等侥蒙,則查找成功暗膜;若給定值小于中間元素,則在中間元素的左半?yún)^(qū)繼續(xù)查找鞭衩;若給定值大于中間元素学搜,則在中間元素的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述過程论衍,直到找到為止瑞佩。
從二分查找的定義我們可以看出,使用二分查找有兩個(gè)前提條件:
(1)待查找的列表必須有序坯台。
(2)必須使用線性表的順序存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)數(shù)據(jù)炬丸。
2、二分查找的代碼實(shí)現(xiàn)
代碼:
BinarySearch.java
public class BinarySearch {
public static void main(String[] args) {
int[] list = {10, 20, 30, 40, 50, 60, 70, 80, 90};
System.out.println("************二分查找************");
display(list);
System.out.println("");
int result = binarySearch(list, 30);
if (result != -1) {
System.out.println("30在列表中的位置是:" + result);
} else {
System.out.println("對(duì)不起捂人,列表中不存在該元素御雕!");
}
}
/**
* 二分查找
*/
public static int binarySearch(int[] list, int key) {
int low = 0;
int high = list.length - 1;
while (low <= high) {
int middle = (low + high) / 2;
// 判斷中間元素是否與給定值相等
if (list[middle] == key) {
return middle;
} else {
if (list[middle] > key) {
// 在中間元素的左半?yún)^(qū)查找
high = middle - 1;
} else {
// 在中間元素的右半?yún)^(qū)查找
low = middle + 1;
}
}
}
// 沒有找到(查找失敗)
return -1;
}
/**
* 遍歷打印
*/
public static void display(int[] list) {
System.out.println("********展示開始********");
if (list != null && list.length > 0) {
for (int num :
list) {
System.out.print(num + " ");
}
System.out.println("");
}
System.out.println("********展示結(jié)束********");
}
}
運(yùn)行結(jié)果: