首先上二分法java實現的代碼
import java.util.Arrays;public class BinarySearch { public static int rank(int key, int[] a) { //數組必須是有序的 int lo = 0; int hi = a.length - 1; while(lo <= hi) { //被查找的鍵要么不存在，要么必然存在于a[lo...hi]之中 int mid = lo + (hi - lo) / 2; if(key < a[mid]) { hi = mid - 1; }else if(key > a[mid]) { lo = mid + 1; }else { return mid; } } return -1; } public static void main(String[] args) { int[] arr = new int[] {1,2,7,5,9,10}; Arrays.sort(arr); System.out.PRintln(Arrays.toString(arr)); int index = BinarySearch.rank(7, arr); System.out.println(index); }}要求：傳入的數組必須是排好序的 邏輯：先將數組分為中間，左邊數組，右邊數組。如果要查找的key正好是中間的則反回索引，如果key 大于 arr[mid],則在右面繼續查找，反之在左面查找。當到達邊界還沒找到時，也就是lo==hi時，lo++ 會大于hi，或者 hi– 會小于lo。則循環終止，返回-1
我們先談談mid值的計算
//如果數組的長度為奇數 數組正好被平均的分為左右兩個要查找數組//如數組為 int[] arr = new int{1,2,3,4,5}//則數組的mid 為 (arr.length - 1) / 2 = 2//mid左邊的數組為{1，2}， 右面為 {4， 5}//如果數組的長度為偶數//如數組為 int[] arr = new int{1,2,3,4,5，6}//則數組的mid 為 (arr.length - 1) / 2 = 2//mid左邊的數組為{1，2}， 右面為 {4， 5， 6}新聞熱點
疑難解答
