java - 使用二分查找查找 key

Question

我正在尝试编写一个程序，该程序使用二分搜索在具有随机生成的数字的数组中查找 key 。当 key 为 0 或非常大的数字时，我无法让程序找到 key 。这是一项家庭作业，但是我碰壁了，无法弄清楚。感谢您提前提供的帮助。

public static int binarySearch(int[] list, int key) {
    int low = 1;
    boolean foundKey = false;
    int high = list.length;
    int i = 0;

    while (high >= low) {
        i = i + 1;
        int mid = (low + high) / 2;

        if (key < list[mid]) {
            high = mid - 1;
        }

        if (key == list[mid]) {
            foundKey = true;
            break;
        }

        low = mid + 1;
    }

    if (foundKey == true)
        System.out.println("Key " + key + " found after " + i + " reads");
    else
        System.out.println("not found");

    return key;
}

Answer 1

需要在您的程序中添加两项更正。

1. int low = 1;这里的low应该从0开始。因此将其设置为int low = 0;。

2. 设置low变量没有条件，只有当您在二分搜索算法中更改搜索方向/部分时才必须执行它，因此添加以下代码

   else if(key > list[mid]) {
       low = mid + 1;
   }
   

3. 在 mid 计算之后添加检查，以确保 mid 指向有效的数组索引，例如

   mid = (low + high)/2;
   if(mid < 0 || mid >= list.length) {
       break;
   }
   

最后，正如您所说的问题评论部分，列表是随机数序列。 这不是二分查找算法的有效输入。输入必须是排序序列，请阅读此二分查找算法 document .