Java實現二分法的案例，什么是二分法

二分法

概念：

• 二分法（Bisection method） 即一分為二的方法，又叫折半查找方法。
• 把一組有序數列分為左右兩部分，從這組數字的中間位置開始找：
• 如果中間位置的數等于目標數，則直接返回；
• 如果中間位置的數大于目標數，則從左邊部分查找；
• 如果小于目標數，則從右邊部分查找；
• 重復以上過程，直到找到滿足條件的記錄，使查找成功。

時間復雜度：
都是 O(log2 N)

空間復雜度：
非遞歸方式： 空間復雜度是O(1);
遞歸方式： 空間復雜度：O(log2N )

實現

1. 遞歸方式

 public static int binarySearchRecursive(int[] arr, int low, int high, int key) {//邊界條件：如果目標數沒有在數組范圍內（即比最左邊的數小，比最右邊的數大）if (arr == null || arr.length == 0 || arr[low] > key || arr[high] < key || low > high) {return -1;}// 獲取中間位置下標int mid = (low + high) / 2;// 將中間位置的數和目標數作比較，如果中間位置的數等于目標數，則直接返回下標，// 如果中間位置的數大于目標數，則將左邊部分用遞歸方法繼續查找；如果小于目標數，則從右邊部分用遞歸方法繼續查找if (arr[mid] == key) {return mid;} else if (arr[mid] > key) {return binarySearch(arr, low, mid - 1, key);} else {return binarySearch(arr, mid + 1, high, key);}}// 測試下：從一組數中找3，輸出數組下標public static void main(String[] args) {int[] arr = {2, 3, 5, 7, 9, 78, 90, 167};System.out.println(binarySearchRecursive(arr, 0, (arr.length) - 1, 3));}

2. 非遞歸方式

 public static int binarySearch(int[] arr, int key) {int low = 0;int high = arr.length - 1;while (low <= high) {int middle = (low + high) / 2;if (key < arr[middle]) {high = middle - 1;} else if (key > arr[middle]) {low = middle + 1;} else {return middle;}}return -1;}// 測試下：從一組數中找3，輸出數組下標public static void main(String[] args) {int[] arr = {2, 3, 5, 7, 9, 78, 90, 167};System.out.println("數組下標："+binarySearch(arr, 3));}

3.非遞歸

/*** 二分查找* @param srcArray 源數組* @param des 目標元素* @return 如果找到則返回索引位置，找不到則返回-1*/
public static int binarySearch(int[] srcArray, int des) {//定義初始最小、最大索引int start = 0;int end = srcArray.length - 1;//確保不會出現重復查找，越界while (start <= end) {//計算出中間索引值  >>> 邏輯右移 也就是 int middle = (end + start)/2int middle = (end + start)>>>1 ;//防止溢出if (des == srcArray[middle]) {return middle;//判斷下限} else if (des < srcArray[middle]) {end = middle - 1;//判斷上限} else {start = middle + 1;}}//若沒有，則返回-1return -1;
}