-2

我有这个代码进行二进制搜索。

public class BinarySearch {

private static int location;
private static int a = 14;
static int[] numbers = new int[]{3, 6, 7, 11, 14, 16, 20, 45, 68, 79};

public static int B_Search(int[] sortedArray, int key) {
    int lowB = 0;
    int upB = sortedArray.length;
    int mid;
    while (lowB < upB) {
        mid = (lowB + upB) / 2;

        if (key < sortedArray[mid]) {
            upB = mid - 1;
        } else if (key > sortedArray[mid]) {
            lowB = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

public static void main(String[] args) {
    BinarySearch bs = new BinarySearch();
   location= bs.B_Search(numbers, a);
   if(location != -1){
       System.out.println("Find , at index of: "+ location);
   }
   else{
       System.out.println("Not found!");
   }
}
}

// 输出：a=14

未找到！！

为什么？

4

3 回答 3

5

首先，值得单步调试调试器中的代码，看看是否能找出问题所在。但是，我从经验中知道，这个特定的错误可能很难诊断。

您需要了解您的上限和下限是包含还是排除。我怀疑上限是独占的，但你的下限是包容的（这很正常）。这意味着：

upB = mid - 1;

实际上应该是：

upB = mid;

我们知道正确的索引不是mid，但它可能是较低的那个。您当前的代码不包括该值...而固定代码仅不包括mid.

正如其他答案所示，您可以改为以不同方式初始化和比较upB，并使其成为包容性上限。就我个人而言，我更喜欢让它独占，因为很多计算机科学都是这样工作的。但两者都会起作用。

现在，请确保您真正了解这里发生了什么。不要只是复制代码并继续前进；弄清楚这一切是如何联系在一起的。

于 2013-03-01T20:57:54.323 回答
3

什么时候lowB == upB，你需要sortedArray[lowB] == key在任意返回之前检查是否-1。

于 2013-03-01T20:58:26.397 回答
3

你用两个不同的东西初始化 upB 。最初它指向结束之后，然后指向最后一个元素：

试试这个：

int upB = sortedArray.length-1;
int mid;
while (lowB <= upB) {
于 2013-03-01T21:01:53.027 回答