我的二进制搜索代码太慢了

Question

我正在尝试解决 this 算法任务。当我提交我的代码时，在某些测试用例上我的代码太慢并且在一些我的代码上给出了错误的输出。我试图找到我犯错的地方，但我真的找不到。因为在我的代码失败的测试用例中，有更多的千长度数组，我无法检查每个输出以发现错误。

所以我想知道你是否可以给我一些建议：

我可以做些什么来提高我的算法效率。
我在某些测试用例上出错的地方我得到了错误的输出。

这是我的代码：

public class Main
{   
public static void main(String[] args)
{
    Scanner sc = new Scanner(System.in);
    int length = sc.nextInt();
    int arr[] = new int[length];

    for(int i=0; i<length; i++)
        arr[i] = sc.nextInt();

    int test = sc.nextInt();
    int type, check;

    for(int i=0; i<test; i++)
    {
        type = sc.nextInt();
        check = sc.nextInt();

        if(type == 0)
        {
            System.out.println(greaterOrEqualThan(arr, check, length));
        }
        else if(type == 1)
        {
            System.out.println(greaterThan(arr, check, length));
        }
    }
}

public static int greaterThan(int arr[],int x, int length)
{
    int low = 0;
    int high = length-1;
    int mid;

    while( low+1 < high)
    {
        mid = (high+low)/2;

        if(arr[mid] <= x)
            low = mid;
        else if(arr[mid] > x)
            high = mid;
    }
    int startIndex;

    if(arr[low] > x && arr[low] != arr[high])
        startIndex = low;
    else if(arr[high] > x && arr[high] != arr[low])
        startIndex = high;
    else
        return 0;

    return length-startIndex;
}

public static int greaterOrEqualThan(int arr[], int x, int length)
{
    int low = 0;
    int high = length-1;
    int mid;

    while(low+1 < high)
    {
        mid = (low+high)/2;

        if(arr[mid] < x)
            low = mid;
        else if(arr[mid] == x)
        {
            high = mid;
            break;
        }
        else
            high = mid;
    }

    int startIndex;

    if(arr[low] >= x)
        startIndex = low;
    else if(arr[high] >= x)
        startIndex = high;
    else
        return 0;

    return length-(startIndex);
}
}

Answer 1

我认为在数组中有多个目标值实例的情况下，您的一种或两种算法可能不正确。（例如 [1,3,3,3,5].

需要考虑的三种情况

考虑三种情况：

x没有出现在数组
x在数组中正好出现一次
x在数组中出现不止一次

如何解决

我建议对这两种方法中的每一种都使用经典的二进制搜索算法（没有修改的精确二进制搜索算法）。之后你做的就是不同的。

所以首先，运行一种经典的二进制搜索算法，直接内联到您的方法中（以便您可以访问 low 和 high 的终端值）。

其次，二分查找结束后，测试是否array[mid] != x。如果array[mid] != x，那么x没有出现在数组中，low == high + 1是真的（因为high和low已经交叉了。因此，计数数组中不小于x的数和数组中大于x的数的个数都等于array.length - low.

第三，如果 array[mid] == x 为真，那么 x 确实在数组中出现了一次或多次。由于经典的二进制搜索算法在找到 x 时立即终止，它是不确定的 "which" x 它终止于

在这种情况下，为了找到不小于 x 的数字计数，您必须使用以下代码片段在数组中找到 "first" x：

do {
    mid = mid - 1;
} while (array[mid] == x);

mid 将是数组中之前 "first" x 元素的索引，因此计数不少于 x 的数字将是 array.length - mid + 1.

同样，为了找到大于x的数字的计数，您必须首先使用以下代码片段在数组中找到"last" x：

do {
    mid = mid + 1;
} while (array[mid] == x);

mid 将是数组中在 "last" x 之后的元素的索引，因此计数大于 x 的数字将是 array.length - mid - 1.

代码

经典二进制搜索的简化、内联版本

int low = 0;
int high = array.length - 1;
int mid = (high + low) / 2;  // priming read

while (array[mid] != x && low <= high) {
    if (array[mid] > x)
        high = mid - 1;
    else   // (array[mid] < x)
        low = mid + 1;
    mid = (high - mid) / 2;
}

不少于x

int countNotLessThan(int[] array, int x)
{
    /* simplified, inlined classical binary search goes here */

    if (array[mid] != x) {
        return array.length - low;
    }

    else {  // array[mid] == x
        do {
            mid = mid - 1;
        } while (array[mid] == x);
        return array.length - mid + 1;
    }
}

大于 x

int countGreaterThan(int[] array, int x)
{
    /* simplified, inlined classical binary search goes here */

    if (array[mid] != x) {
        return array.length - low;
    }

    else {  // array[mid] == x
        do {
            mid = mid + 1;
        } while (array[mid] == x);
        return array.length - mid - 1;
    }
}

我的二进制搜索代码太慢了

My binary search code is too slow

java

algorithm

binary-search

需要考虑的三种情况

如何解决

代码

经典二进制搜索的简化、内联版本

不少于x

大于 x