c - 如何返回正事件

Question

我有一个函数，当给定一个由 N 个整数组成的零索引数组 A(按非递减顺序排序)和一些整数 X 时，我会在 A 中查找 X。如果 A 中存在 X，则它返回一个正索引X 在 A 中的出现。否则，函数返回 -1。

它应该像这样工作:

• 如果我有 A[0]=1、A[1]=1 和 X=1，它应该返回 0，因为 A[0]=1。

但它没有返回我想要的。有人能帮我吗？ 这是我的代码:

int Number(int *A, int N, int X) {
    int r, m, l;
    if (N == 0) {
        return -1;
    }
    l = 0;
    r = N - 1;
    while (l < r) {
        m = (l + r) / 2;
        if (A[m] > X)  {
            r = m - 1;
        } else {
            l = m;
        }
    }
    if (A[l] == X) {
        return l;
    }
    return -1;
}

Answer 1

二分搜索不保证找到的位置是该数字在数组中的第一次出现。

if I have A[0]=1, A[1]=1 and X=1 it should return 0 because A[0]=1

这意味着在这个例子中答案“1”是正确的，因为 A[1] = 1 也是如此。

您需要手动遍历数组以找到第一个不匹配 值(或数组开头)。优化是可能的，但只有当您有一个具有大量值重复的非常大的数组时才需要优化。

您也可以尝试默认的二进制搜索方法:

int Number(int *A, int N, int X) {
    int r, m, l;
    if (N == 0) {
        return -1;
    }
    l = 0;
    r = N - 1;
    while (l < r) {
        m = (l + r) / 2;
        if (A[m] == X)
           return m;
        if (A[m] > X)  {
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    return -1;
}