適用場景

適用于有序數組中查找某一個值.
每查找一次,就將搜尋范圍縮小一半,
平均時間復雜度是O(logN), 簡記作:O(lgN).

主要難點

主要難點在于邊界條件的判斷；

大致思路:

1.當供查找的數組不合法時,直接返回結果,查詢無果;

2.當數組長度等于1時,直接判斷是否相等即可；

3.當數組僅有兩個元素時,直接分別判斷；

4.當數組元素多于2個時, 采用如下策略:

1) 有限比較數組頭尾兩個元素與查詢目標元素的值比較, 因為是有序數組,如果在界外,則直接判斷給出查詢結果；

2)如果和邊界元素比較后,范圍在界內,則開始真正的二分查找法,分別采用low, high, mid三個游標來界定查詢范圍.

實現方式

1.迭代法

2.遞歸法

3.Arrays.binarySearch(int[] arr, int target) API

實踐代碼如下:

import java.util.Arrays;/*** 默認有序數組arr[]是從小到大的順序排列的,如果不是則需要先結合排序算法使用.*/
public class BinarySearch {// 迭代法public int binarySearch1(int[] arr, int target) {// 先判斷數據的有效性if (arr == null || arr.length < 1) {return -1;}int low = 0;final int length = arr.length;int high = length - 1;int mid;// System.out.println("length:" + length + ",low:" + low + ",high:" + high//         + ",mid:" + (low + high) / 2);// 先判斷頭尾游標的值if (length == 1) {if (arr[0] == target) {return 0;} else {return -1;// not found}} else { // length >= 2if (arr[low] == target) {return low;} else if (arr[high] == target) {return high;} else if (arr[low] > target || arr[high] < target) {//如果待查找的數值在有序數組最大或者最小值之外,直接判查詢未果,無須再二分查找了.return -1;}}while (low < high) {mid = (low + high) / 2;// System.out.println("low:" + low//         + ",value[low]:" + arr[low]//         + ",high:" + high + ",value[high]:" + arr[high]//         + ",mid:" + mid + ",value[mid]:" + arr[mid]);//這段非常重要,否則將可能出現死循環,//當頭游標和尾游標的中間值已經是起始或者末尾兩個游標位之一時,代表查找結束,且無果.if (high == mid || low == mid) {return -1;}if (arr[mid] < target) {low = mid;} else if (arr[mid] > target) {high = mid;} else if (arr[mid] == target) {return mid;}}return -1;}// 遞歸法public int binarySearch2(int[] arr, int target) {// System.out.println("enter binarySearch2");if (null == arr || arr.length < 1) {return -1;}final int length = arr.length;if (length == 1) {if (arr[0] == target) {return 0;} else {return -1;// not found}} else { // length >= 2if (arr[0] == target) {return 0;} else if (arr[arr.length - 1] == target) {return arr.length - 1;} else if (arr[0] > target || arr[length - 1] < target) {return -1;// not found}}return binarySearchRecursion(arr, 0, arr.length - 1, target);}private int binarySearchRecursion(int arr[], int low, int high, int target) {// System.out.println("length:" + arr.length + ",low:" + low + ",high:" + high//         + ",mid:" + (low + high) / 2);int mid;while (low < high) {mid = (low + high) / 2;//這段非常重要,否則將可能出現死循環,//當頭游標和尾游標的中間值已經是起始或者末尾兩個游標位之一時,代表查找結束,且無果.if (mid == low || mid == high) {return -1;}if (arr[mid] == target) {return mid;} else if (arr[mid] < target) {return binarySearchRecursion(arr, mid, high, target);} else if (arr[mid] > target) {return binarySearchRecursion(arr, low, mid, target);}}return -1;}// Arrays.binarySearch API法public int binarySearchArrays(int[] arr, int target) {if (arr == null || arr.length <= 0) {return -1;}//Arrays.sort(arr);return Arrays.binarySearch(arr, target);}public static void main(String[] args) {// 多個測試用例數組int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,};int[] arr2 = {1, 2, 4,};int[] arr3 = {1, 2, 4, 6};int[] arr4 = {1, 2, 4, 6, 8};int[] bigArr = new int[10000];for (int i = 0; i < 10000; i++) {bigArr[i] = i * 2;}System.out.println("init arr done!");int wanted = 6;int[] toBeSearchArr = bigArr;BinarySearch bs = new BinarySearch();System.out.println("binearySearch1 :" + bs.binarySearch1(toBeSearchArr, wanted));System.out.println("binearySearch2 recursion :" + bs.binarySearch2(toBeSearchArr, wanted));System.out.println("Arrays.binarySearch():" + bs.binarySearchArrays(toBeSearchArr, wanted));}
}

測試結果如下:

init arr done!
binearySearch1 :3
binearySearch2 recursion :3
Arrays.binarySearch():3[Done] exited with code=0 in 1.508 seconds