如何在排序数组上使用二进制搜索来查找特定范围内的整数数。 （有重复） [英] How to use a binarysearch on a sorted array to find the number of integers within a certain range. (with duplicates)

问题描述

假设你有一个排序的整数数组：

Say you have a sorted array of integers:

{3,4,4,6,10,15,15,19,23,23,24,30}

你想找到整数的数量落在4和23的范围内。

And you want to find the number of integers that fall within a range of 4 and 23.

{4,4,6,10,15,15,19,23,23}

因此结果为9。

我写了一个二进制搜索实现，但我不确定如何修改它以考虑到可以有多个整数匹配范围的上限这一事实。

I wrote a binarysearch implementation, but I'm not sure how I would modify it to also take into account the fact that there can be multiple integers that match the upper bounds of the range.

我想在方法签名中添加一个布尔值来询问是否要查找键的上限，但我不确定是否可以在保持O（log）的同时在单个方法中完成（N））复杂性。

I thought of adding a boolean in the method signature to ask whether to look for the upper bounds of the key, but I'm not sure if it can be done in a single method while keeping O(log(N)) complexity.

或者是否有其他方法在O（log（N））时间内在排序数组中找到该范围内的项目数？

Or is there some other way of finding the # of items in that range in the sorted array in O(log(N)) time?

这是我到目前为止：

int start = rangeBinarySearch(arr, 4, false);
int end = rangeBinarySearch(arr, 23, true); // true would indicate that I want the position of the last occurrence of the key.

int totalInRange = (Math.abs(end) - Math.abs(start) -1)


private static int rangeBinarySearch(int[] items, int key, boolean lastIndex) {
    if(items == null)
        throw new IllegalArgumentException();

    int start = 0;
    int end = items.length - 1;

    while(start <= end) {
        int mIndex = (start + end) / 2;
        int middle = items[mIndex];

        if(middle < key)
            start = (mIndex +1);
        else if(middle > key)
            end = (mIndex -1);
        else
            return mIndex; // Possible something here to find the upper bounds?
    }

    return -(start +1);
}

推荐答案

范围二进制搜索较低绑定和上限是不同。这里不同意味着他们有不同的停止标准和返回步骤。

Range binary search for the lower bound and the upper bound are different. Here different means they have different stopping criteria and return step.

1. 对于较低的绑定（左范围），您可以调用以下函数来获取值大于或等于它的排序数组中的索引，否则为-1。

1. For the lower bound (left range), you can call the following function to get the index in the sorted array where the value is larger or equal than it, -1 otherwise.

int binarySearchForLeftRange(int a[], int length, int left_range)
{
    if (a[length-1] < left_range)
        return -1;

    int low = 0;
    int high = length-1;

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

        if(a[mid] >= left_range)
            high = mid-1;
        else //if(a[mid]<i)
            low = mid+1;
    }

    return high+1;
}

上限（右边），你可以调用以下函数来获取值小于或等于它的排序数组中的索引，否则为-1。

For the upper bound (right range), you can call the following function to get the index in the sorted array where the value is smaller or equal than it, -1 otherwise.

int binarySearchForRightRange(int a[], int length, int right_range)
{
    if (a[0] > right_range)
        return -1;

    int low = 0;
    int high = length-1;

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

        if(a[mid] > right_range)
            high = mid-1;
        else //if(a[mid]<i)
            low = mid+1;
    }

    return low-1;
}

最后，如果你想得到这个范围内的元素数量，根据上述两个函数的返回值很容易。

Finally, if you want to get the number of how many elements within this range, it's easy based on return values of these two above functions.

int index_left = binarySearchForLeftRange(a, length, left_range);
int index_right = binarySearchForRightRange(a, length, right_range);

if (index_left==-1 || index_right==-1 || index_left>index_right)
    count = 0;
else
    count = index_right-index_left+1;

---

测试 :(有重复）

    int a[] = {3,4,4,6,10,15,15,19,23,23,24,30};
    int length = sizeof(arr)/sizeof(arr[0]);

    int left_range = 4;
    int right_range = 23;
    int index_left = binarySearchForLeftRange(a, length, left_range); // will be 1
    int index_right = binarySearchForRightRange(a, length, right_range); // will be 9

    int count; // will be 9
    if (index_left==-1 || index_right==-1 || index_left>index_right)
        count = 0;
    else
        count = index_right-index_left+1;

---

编辑：当然，你可以通过传递一个额外的标志来将前两个函数合并为一个，以指示它是下限或上限，但如果没有则更清楚。你的选择！

---

EDIT: Of course, you can merge the first two functions into one by passing one extra flag to indicate it as lower bound or upper bound, though it will be much more clear if not. Your choice!

这篇关于如何在排序数组上使用二进制搜索来查找特定范围内的整数数。 （有重复）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！