java - 使用 Recusion 进行二分搜索

Question

我正在尝试使用 Java 中的递归创建二进制搜索算法，当调试一切似乎都很好，直到它找到值并应该返回所需键的索引。但是，由于某种原因，它会跳过 return 语句并转到底部的 return 语句。

public int binSearch(int key, int L, int R) {

    int mid =(R + L)/2;

    if (R < L) {
        return -1;
    }

    if (A[mid] == key) {
        return mid;
    }

    if (key > A[mid]) {
        binSearch(key, mid + 1, R);
    }

    if (key < A[mid]) {
        binSearch(key, L, mid - 1);
    }
   return -1;
}

标签： javasearchbinary

Answer 1

我能够从一个旧帖子中挽救这个。我知道它不能解决您的问题，但它向您展示了解决此问题的另一种方法。

public static int binarySearch(int[] a, int target) {
    return binarySearch(a, 0, a.length-1, target);
}

public static int binarySearch(int[] a, int start, int end, int target) {
    int middle = (start + end) / 2;
    if(end < start) {
        return -1;
    } 

    if(target==a[middle]) {
        return middle;
    } else if(target<a[middle]) {
        return binarySearch(a, start, middle - 1, target);
    } else {
        return binarySearch(a, middle + 1, end, target);
    }
}