申論題

二元搜尋法（Binary Search）是一種在有序陣列中尋找特定元素的快速搜尋算法。該算法每次搜尋都將搜尋範圍減半，從而實現對數時間複雜度的搜尋效率。下面是一個使用遞迴法實現二元搜尋的函式示例，假設陣列是按照升序排列的。

java

public class BinarySearch {

    /**
     * 使用遞迴法進行二元搜尋
     *
     * @param A 有序陣列
     * @param L 搜尋範圍的左邊界
     * @param R 搜尋範圍的右邊界
     * @param K 需要搜尋的鍵值
     * @return 鍵值在陣列中的索引，如果不存在則返回-1
     */
    public static int binarySearch(int[] A, int L, int R, int K) {
        if (L <= R) {
            int mid = L + (R - L) / 2; // 避免整數溢出的寫法

            // 如果鍵值正好是中間元素
            if (A[mid] == K) {
                return mid;
            }

            // 如果鍵值小於中間元素，則只需在左半邊進行搜尋
            if (K < A[mid]) {
                return binarySearch(A, L, mid - 1, K);
            }

            // 否則在右半邊進行搜尋
            return binarySearch(A, mid + 1, R, K);
        }

        // 如果範圍不合法，表示元素不存在
        return -1;
    }

    public static void main(String[] args) {
        int[] A = {2, 3, 4, 10, 40}; // 示例陣列
        int K = 10; // 要搜尋的鍵值
        int result = binarySearch(A, 0, A.length - 1, K);

        if (result == -1) {
            System.out.println("Element not present");
        } else {
            System.out.println("Element found at index " + result);
        }
    }
}
在這個實現中，如果搜尋範圍有效（即左邊界不大於右邊界），我們首先找到中間元素的索引mid。如果中間元素就是我們要找的鍵值K，則直接返回mid。否則，我們根據鍵值與中間元素的比較結果，決定是繼續在左半部分還是右半部分進行搜尋，從而達到將搜尋範圍減半的目的。如果在給定的搜尋範圍內沒有找到鍵值，則函式返回-1，表示鍵值不在陣列中。