3

ソートされた整数の配列があるとします。

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

そして、4 から 23 の範囲内にある整数の数を見つけたいとします。

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

したがって、結果は 9 になります。

バイナリサーチの実装を作成しましたが、範囲の上限に一致する整数が複数存在する可能性があるという事実を考慮して、それをどのように変更すればよいかわかりません。

メソッドシグネチャにブール値を追加して、キーの上限を探すかどうかを尋ねることを考えましたが、O(log(N)) の複雑さを維持しながら単一のメソッドで実行できるかどうかはわかりません。

または、ソートされた配列内のその範囲内のアイテムの数を O(log(N)) 時間で見つける他の方法はありますか?

これは私がこれまでに持っているものです:

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);
}
4

3 に答える 3

2

下限と上限の範囲二分探索は異なります。ここで異なるとは、停止基準と戻りステップが異なることを意味します。

  1. 下限 (左側の範囲) については、次の関数を呼び出して、並べ替えられた配列内で値がそれより大きいか等しいインデックスを取得できます。それ以外の場合は -1 です。

    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;
}

  2. 上限 (右の範囲) については、次の関数を呼び出して、値がそれより小さいか等しいソート済み配列のインデックスを取得できます。それ以外の場合は -1 です。

    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;
}

  3. 最後に、この範囲内の要素数を取得したい場合は、上記の 2 つの関数の戻り値に基づいて簡単に取得できます。

    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;

編集: もちろん、最初の 2 つの関数を 1 つにマージして、1 つの追加フラグを渡して下限または上限として示すことができますが、そうでない場合ははるかに明確になります。あなたの選択！

于 2013-12-20T12:26:33.350 に答える
0

2 つのバイナリ検索を実行して、rangeLow の前の最低インデックスと rangeHigh の後の最高インデックスを見つける必要があります。これにより、範囲内の重複をカウントできます。

二分探索を 2 回実行するため、これにより時間の複雑さが o(2 log n) になります。

private int searchArrayForNumbersInRange(int[] arr, int start, int end) {
    int leftIndex = searchLeft(arr, start);
    int rightIndex = searchRight(arr, end);
    int count;

    if (leftIndex < 0 || rightIndex < 0)
        return -1;
    if (rightIndex == leftIndex)
        count = 1;
    else {
        count = rightIndex - leftIndex;
    }
    return count;
}

private int searchLeft(int[] arr, int start) {
    int lo = 0;
    int hi = arr.length - 1;

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

        if (arr[mid] == start && arr[mid -1] < start) {
            return mid - 1;
        }

        if (arr[mid] >= start)
            hi = mid - 1;
        else
            lo = mid + 1;
    }

    return -1;
}

private int searchRight(int[] arr, int end) {
    int lo = 0;
    int hi = arr.length -1;

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

        if (arr[mid] == end && arr[mid+1] > end)
            return mid;

        if (mid <= end)
            lo = mid + 1;
        else
            hi = mid - 1;
    }

    return -1;
}
于 2013-10-14T05:03:50.367 に答える
0

アルゴリズムを学習していない場合は、代わりに標準関数を使用します。

    Arrays.binarySearch

基本的に、最初の要素 (4) の最初の出現と最後の (23) の最後の出現と減算が必要です。しかし、(4) がそこにある必要はないので、Arrays.binarySearch のドキュメントを読んでください。(4) がどこにあるかがわかります。

多くの (4) が予想される場合は、独自の binSearch を作成する必要があります。これにより、最初と最後のインデックスの両方が返されます。

インデックス i での最初の出現を見つける 前の 1 つがある場合は i/2 を見て、(4) がある場合は i/4 を見て、そうでない場合は 3*i/4 を見て ...

于 2013-03-08T10:13:08.640 に答える