Java實現二分查找演算法

二分查找:
兩種方式: 非遞歸方式和遞歸方式
主要思路: 對於已排序的數組(先假定是從小到大排序), 先定義兩個"指針", 一個"指向"首元素low, 一個"指向"末尾元素high.
然後, 開始折半比較, 即讓要查找的數與數組中間的元素(索引為 low+high/2)比較. 若要查找的數比中間數小,
說明要查找的數在數組左側(註意前提是數組從小到大排序), 否則說明該數在數組的右側. 如果low最後還比high大,
倆"指針"交叉了, 說明沒有找到該數, 即數組不存在該數.

註意事項: 排序規則與數組的排序順序有關, 即從大到小排序和從小到大排序是不一樣的!!!

 1 class BinarySearch {
 2     
 3     // 二分查找非遞歸方式
 4     // arr 給定已排序數組
 5     // num 要查找的數
 6     public static int search(int[] arr, int num) {
 7         int low = 0;
 8         int high = arr.length - 1;
 9         int mid = 0;
10         while (low <= high) {
11             mid = (low + high) / 2;
12             if (num < arr[mid]) {
13                 high = mid - 1;
14             }
15             
16             if (num > arr[mid]) {
17                 low = mid + 1;
18             }
19             if (num == arr[mid]) {
20                 return mid;
21             }
22         }
23         return -1;    // 沒找到
24     }
25     
26     
27     // 二分查找遞歸方式
28     // arr 給定已排序數組
29     // num 要查找的數
30     // low 初始左側指針 指向第一個元素
31     // high 初始末尾指針 指向最後一個元素
32     public static int binarySearch(int[] arr, int num, int low, int high) {
33         
34         int mid = (low + high) / 2; 
35         
36         // 遞歸結束條件
37         if (low > high) {
38             return -1;
39         }
40         
41         if (num < arr[mid]) {
42             return binarySearch(arr, num, low, mid - 1);
43         } else if (num == arr[mid]) {
44             return mid;
45         } else {
46             return binarySearch(arr, num, mid + 1, high);
47         }
48         
49     }
50     
51     
52     public static void main(String[] args) {
53         
54         // 給定數組 從小到大排序.
55         int[] arr = {2, 3, 5, 7, 8, 9, 11, 12, 15};
56         // int[] arr = {15, 12, 11, 9, 8, 7, 5, 3, 2};
57         
58         int m = 3;
59         
60         // int index = search(arr, m);
61         
62         int index = binarySearch(arr, m, 0, arr.length - 1);
63         
64         System.out.println(index);
65         
66     }
67     
68 }