二分法定義：
對(duì)于區(qū)間[a，b]上連續(xù)不斷且f（a）·f（b）<0的函數(shù)y=f（x）婉商，通過不斷地把函數(shù)f（x）的零點(diǎn)所在的區(qū)間一分為二，使區(qū)間的兩個(gè)端點(diǎn)逐步逼近零點(diǎn)，進(jìn)而得到零點(diǎn)近似值的方法叫二分法繁莹。（百度百科）
給定一個(gè)數(shù)組，我們要查找當(dāng)前數(shù)據(jù)在數(shù)組中的位置特幔，雖然可以使用循環(huán)一個(gè)個(gè)遍歷咨演，但是由于要使代碼運(yùn)行時(shí)間盡可能的小，所以我們要采用二分法來查找蚯斯。
先上代碼：
public class BinarySearch {
/**
* Searches element k in a sorted array.
* @param arr a sorted array
* @param k the element to search
* @return index in arr where k is. -1 if not found.
*/
public int binarySearch(int[] arr, int k) {
int a = 0;
int b = arr.length;
// Loop invariant: [a, b) is a valid range. (a <= b)
// k may only be within range [a, b).
while (a < b) {
int m = a + (b - a) / 2; // m = (a + b) / 2 may overflow!
if (k < arr[m]) {
b = m;
} else if (k > arr[m]) {
a = m + 1;
} else {
return m;
}
}
return -1;
}
public static void main(String[] args) {
BinarySearch bs = new BinarySearch();
System.out.println("Testing normal data");
System.out.println(
bs.binarySearch(new int[]{1, 2, 10, 15, 100}, 15));
System.out.println(
bs.binarySearch(new int[]{1, 2, 10, 15, 100}, -2));
System.out.println(
bs.binarySearch(new int[]{1, 2, 10, 15, 100}, 101));
System.out.println(
bs.binarySearch(new int[]{1, 2, 10, 15, 100}, 13));
System.out.println("======");
System.out.println("Testing empty or singleton data.");
System.out.println(
bs.binarySearch(new int[]{}, 13));
System.out.println(
bs.binarySearch(new int[]{12}, 13));
System.out.println(
bs.binarySearch(new int[]{13}, 13));
System.out.println("======");
System.out.println("Testing data of size 2.");
System.out.println(
bs.binarySearch(new int[]{12, 13}, 13));
System.out.println(
bs.binarySearch(new int[]{12, 13}, 12));
System.out.println(
bs.binarySearch(new int[]{12, 13}, 11));
}
當(dāng)使用二分查找的時(shí)候有幾個(gè)注意點(diǎn)：
1薄风、當(dāng)前數(shù)據(jù)長(zhǎng)度是否大于1。
2拍嵌、數(shù)組的長(zhǎng)度范圍如何去定義遭赂。
3、在使用二分的時(shí)候横辆，如果數(shù)組長(zhǎng)度過大撇他，數(shù)組收尾相加數(shù)據(jù)過大，導(dǎo)致數(shù)據(jù)溢出咋辦龄糊。
解決 第一個(gè)問題：
我們首先判斷數(shù)組的尾減去數(shù)組的頭看是否大于"0"
第二個(gè)問題：
我們將數(shù)組.length當(dāng)成數(shù)組的尾逆粹，而不是數(shù)組.length-1，大家都知道數(shù)組下標(biāo)是從"0"開始的炫惩，但是為什么不用數(shù)組.length-1呢僻弹？
我們直接使用數(shù)組.length的時(shí)候可以形成一個(gè)左閉右開區(qū)間，方便數(shù)組相加他嚷。如：[a,b）+[b,c) =[a,c)
而且我們直接使用數(shù)組.length的時(shí)候判斷左邊的時(shí)候直接小于就行蹋绽，不用再去判斷等于條件。
第三個(gè)問題：
c = ( a + b ) / 2
當(dāng)a和b過大的時(shí)候筋蓖，a + b的數(shù)據(jù)就更大卸耘，導(dǎo)致數(shù)據(jù)溢出咋辦，這個(gè)時(shí)候我們選擇使用
c = a + (b - a) / 2
來解決這個(gè)問題粘咖。
上面代碼運(yùn)行結(jié)果：
