二进制搜索变体中的无限循环 (Java)

Question

我的目标是输入一个键和一个数组，然后使用二进制搜索输出该数组中小于或等于键的值的数量。

这是我的代码：

import java.util.*;
import java.io.*;

public class search {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int key = scan.nextInt();
        int size = scan.nextInt();
        int [] array = new int [size];

        for (int i = 0;i < size ;i++ ) {
            array[i] = scan.nextInt();
        }
        Arrays.sort(array);

        System.out.println(binary(key, array));
    }

    public static int binary (int key, int [] array){
        int lo = 0;
        int hi = array.length - 1;

        while (lo < hi){
            int mid = (lo + hi) / 2;
            if (array[mid] <= key){
                lo = mid;
            }

            else {
                hi = mid - 1;
            }
        }

        return lo + 1;
    }
}

数据键 = 5，数组 = {2,4,6,7}，程序运行良好。但是当有 three 个值小于或等于密钥时，它就会失控。例如，key = 5, array = {2,4,5,6} 会产生无限循环。我找到了这个原因，但我不知道如何解决它。

基本上 mid 值一直计算为相同的值。我该怎么做才能解决这个问题？如果代码本质上是错误的，那就意味着 the set solution for a USACO problem 是错误的。

Answer 1

您的算法似乎没问题。但我看到为 mid 分配值时出现问题。

int mid = (hi+lo)/2

想想你的

hi=4
mid = 3

现在 mid 的新值将是 (3+4)/2 = 3（整数除法）

所以循环将继续运行而不会中断。

在这种情况下，您可以通过检查此条件来增加 mid 的值。

但更有效的方法似乎是检查 mid 的值是否重复，然后打破循环。最后检查array[hi]的值是否和你的array[mid]

一样

希望这会有所帮助..

祝你有愉快的一天.. :)

编辑

更好的做法是

将您的 while 循环更改为

while(mid<hi+1){
 }

然后检查循环后的值是否相等..

或只需设置

  mid = (mid+hi+1)/2

Answer 2

示例解决方案似乎不错。您的代码的问题是 mid = (lo + hi) / 2 向 lo 舍入，这是一个问题，因为更新案例是 lo = mid 和 hi = mid - 1。当hi == lo + 1时，第一种情况，没有任何进展。您应该像示例那样四舍五入：mid = (lo + hi + 1) / 2（警告：可能会在长数组上溢出；检查您的约束）。

示例还检查第一个值是否小于键。

Answer 3

在你的循环中，你必须让你的间隔越来越小，你还必须排除你刚刚看过的元素。当你向左走时你会这样做，但当你向右走时则不会。

您还错过了长度为 1 的区间，因为您使用了包含的下限和上限。你的循环条件应该是 lo <= hi.

最后，你return太多了：当key小于第一个元素时结果应该是0，当它大于最后一个元素时应该是数组长度

所以：

static int binary(int key, int[] array)
{
    int lo = 0;
    int hi = array.length - 1;

    while (lo <= hi) {
        int mid = (lo + hi) / 2;

        if (array[mid] <= key) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    return lo;
}

在我看来，最好使用独占上限，就像 Java 通常那样。（例如，一个长度为n的数组，其元素位于indoces 0到n - 1，上限n超出了有效范围。）如果不出意外，它与其他Java代码。所以：

static int binary(int key, int[] array)
{
    int lo = 0;
    int hi = array.length;

    while (lo < hi) {
        int mid = (lo + hi) / 2;

        if (array[mid] <= key) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }

    return lo;
}

二进制搜索变体中的无限循环 (Java)

Infinite loop in binary search variant (Java)

java

arrays

algorithm

binary-search

infinite-loop