在 C 中使用 O(log(N)) 查找排序数组中数字的出现次数？

Question

如果我有一个排序数组 arr[] 包含 n 个元素，我怎样才能找到复杂度为 O(logn) 的某个数字 key 的出现次数？

例如：对于

int arr[] = {0, 1, 2, 2, 6, 6, 6, 7};
int n = 8;
int key = 6;
int first, last;

我会得到3.

我解决这个问题的方法是进行两次二进制搜索，一次搜索第一次出现 key 的索引，将结果保存在 int first 中。另一个搜索key最后一次出现的索引，将结果保存在last中。那么剩下要做的就是return last - first + 1.

但是当我开始编写问题代码时，我遇到了一个问题，我无法计算last 是什么导致了奇怪的结果。我一直在尝试调试我的代码但没有成功，有什么建议吗？

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

int ex2(int*, int, int);

int main()
{
    int arr[] = {1, 4, 6, 6, 6, 7, 7, 8, 11, 14, 22};
    printf("%d", ex2(arr, 11, 6));
    return 0;
}

int ex2(int* a, int n, int x)
{
    int low = 0, high = n - 1, mid, first = 0, last = 0;
    // bin first
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (a[mid] == x)
        {
            if (mid - 1 < low || a[mid - 1] < x)
            {
                first = mid;
                break;
            }
            else
                high = mid - 1;
        }
        if (a[mid] < x)
            low = mid + 1;
        else
            high = mid - 1;
    }
    // bin last
    low = 0;
    high = n - 1;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (a[mid] == x)
        {
            if (mid + 1 > high|| a[mid + 1] > x)
            {
                last = mid;
                break;
            }
            else
                low = mid + 1;
        }
        if (a[mid] < x)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return last - first + 1;

}

当我运行它用于：

    int arr[] = {1, 4, 6, 6, 6, 7, 7, 8, 11, 14, 22};
    printf("%d", ex2(arr, 11, 6));

我得到 -1（因为 last 仍然是 0 不像 first 持有 2 的正确值 - > 0 - 2 + 1 = -1 ). 当我得到 3（6 出现 3 次）时。

Answer 1

将出现的两个地方 if (a[mid] < x) 更改为 else if (a[mid] < x)。

否则，在 a[mid] == x 并且您设置 low（在第一次搜索中）或 high（在第二次搜索中）的情况下，代码将落入此a[mid] < x 的测试并错误地设置了另一个边界。插入 else 排除那个。

在 C 中使用 O(log(N)) 查找排序数组中数字的出现次数？

Finding the number of occurrences of a number in a sorted array with O(log(N)) in C?

c

binary-search