寫在前邊的話：今天記錄一下關(guān)于算法中 二分查找 的一些理解和心得待笑。
主要分為以下幾個(gè)方面分享
- 二分查找的思想
- 實(shí)現(xiàn)方式
- 時(shí)間復(fù)雜度
二分查找的思想
1：在一個(gè) 有序且采用順序結(jié)構(gòu)存儲(chǔ)的線性表中，取 中間記錄 與 給定對(duì)象 相比較页藻。
2：若 中間記錄與給定對(duì)象值 相等，則表示查找成功膝擂，并返回中間記錄的下標(biāo)哎壳。
3：若 中間記錄比給定對(duì)象值 小，則在中間記錄的 右半?yún)^(qū)繼續(xù)查找充石。
4：若 中間記錄比給定對(duì)象值 大，則在中間記錄的 左半?yún)^(qū)繼續(xù)查找。
5：不斷重復(fù)上述1~4步驟骤铃，直至查找成功或者失敗為止拉岁。
實(shí)現(xiàn)方式
public static void main(String[] args){
Integer[] array = Util.createRandomArray(100, 20);
Util.sysSort(array);
Integer[] array1 = Arrays.copyOf(array, array.length);
Integer[] array2 = Arrays.copyOf(array, array.length);
Util.print(Arrays.toString(array) + "================================", "數(shù)據(jù)源");
int searchNum = 37;
int index = binarySearch(array1, searchNum);
Util.print("結(jié)果:" + (index >= 0 ? "找到" + searchNum + ",它的下標(biāo)為:" + index : "沒找到！"), "binarySearch()");
Util.print("================================", "");
int index2 = Util.sysBinarySearch(array2, searchNum);
Util.print("結(jié)果:" + (index2 >= 0 ? "找到" + searchNum + ",它的下標(biāo)為:" + index2 : "沒找到惰爬！"), "Util.sysBinarySearch()");
}
private static int binarySearch(Integer[] array, Integer searchNum){
Util.checkArrayISNull(array);
Util.checkSrcIsNull(searchNum);
int searchNumIndex = -1;
int low = 0; //記錄查找區(qū)域的最小邊界值
int high = array.length - 1; //記錄查找區(qū)域的最大邊界值
while (low <= high){
int mid = (low + high) >> 1; //中間記錄的下標(biāo)
System.out.println("low:" + low + ", high:" + high + ", mid:" + mid);
if(searchNum < array[mid]){ //給定值比中間記錄小喊暖，說明給定值在中間記錄的左半?yún)^(qū)域，此時(shí)high對(duì)應(yīng)的下標(biāo)應(yīng)該是mid的前一位數(shù)據(jù)對(duì)應(yīng)的下標(biāo)
high = mid - 1;
} else if(searchNum > array[mid]){ //給定值比中間記錄大撕瞧，說明給定值在中間記錄的右半?yún)^(qū)域陵叽，此時(shí)low對(duì)應(yīng)的下標(biāo)應(yīng)該是mid的后一位數(shù)據(jù)對(duì)應(yīng)的下標(biāo)
low = mid + 1;
} else { //查找成功
searchNumIndex = mid;
break;
}
}
return searchNumIndex;
}
public static int sysBinarySearch(Integer[] src, Integer searchNum){
checkArrayISNull(src);
checkSrcIsNull(searchNum);
int index = -1;
index = Arrays.binarySearch(src, searchNum);
return index;
}
log
數(shù)據(jù)源:[6, 10, 12, 17, 18, 24, 26, 33, 37, 42, 46, 47, 51, 55, 66, 66, 69, 70, 82, 95]================================
low:0, high:19, mid:9
low:0, high:8, mid:4
low:5, high:8, mid:6
low:7, high:8, mid:7
low:8, high:8, mid:8
binarySearch():結(jié)果:找到37,它的下標(biāo)為:8
:================================
Util.sysBinarySearch():結(jié)果:找到37,它的下標(biāo)為:8
時(shí)間復(fù)雜度
O(logn)
