引言

二分法，顧名思義，即一分為二的方法，通常用于判斷在某個有序數列中是否存在某個數，由于其優秀的算法思想，時間復雜度一般都是 O(logN) ，通常要 O(N) 的遍歷方式更加優秀。

一、經典二分法查找

最常見的二分查找是有序數列找某數，但并不是所有二分查找都必須有序。

public static boolean exist(int[] sortedArr, int num) {if (sortedArr == null || sortedArr.length == 0) return false;// 設置邊際int L = 0, mid = 0, R = sortedArr.length - 1;// L .. Rwhile (L < R) {// 計算midmid = L + ((R - L) >> 1);if (sortedArr[mid] == num) {return true;} else if (sortedArr[mid] > num) {// 棄右留左R = mid - 1;} else {// 棄左留右L = mid + 1;}}return sortedArr[L] == num; }

二、其他二分查找題目

題目：給定一個有序數組，找 >= 某數最左側的位置，例如，arr{1,2,3,3,3,4,4,6,9},即找到位置 2。

public static int mostLeftIndex(int[] arr, int num) {int L = 0, R = arr.length - 1;int mostLeftIndex = 0;while (L < R) {mostLeftIndex = L + ((R - L) >> 1);if (arr[mostLeftIndex] >= num) {// 棄右留左R = mostLeftIndex - 1;} else {// 棄左留右L = mostLeftIndex + 1;}}if (arr[L] == num)return L;elsereturn L + 1; }

題目2：局部最小問題，在無序數組中，任意相鄰兩個數不相等，只要比相鄰的數都小，就是局部最小，找到并返回這樣一個局部最小值的位置。

例如，若[0]<[1]，則[0]就是局部最小，[len-2]>[len-1] 則[len-1]就是局部最小， [i-1]>[i]<[i+1]，那么[i]就是局部最小。

public static int partialMin(int[] arr) {if (arr[0] < arr[1])return 0;if (arr[arr.length - 2] > arr[arr.length - 1])return arr.length - 1;int L = 1;int R = arr.length - 2;int mid = 0;while (L < R) {mid = L + ((R - L) >> 1);if (arr[mid] > arr[mid + 1]) {// 棄左留右L = mid + 1;} else if (arr[mid] > arr[mid - 1]){// 棄右留左R = mid - 1;} else {return mid;}}return L; }

局部最小問題解析，首先判斷 0 和最后一個位置上的數是否為最小，如果都不是，那么在兩者中間一定存在一個局部最小。二分，然后看中間位置是否比一側大，取大于一側的區間，就形成了最開始的“兩端都不是最小，那么中間一定存在一個最小” 這樣的結構。

?

總結

以上是生活随笔為你收集整理的查找算法——二分法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。