包含二分查找与while循环的findingDup算法的时间复杂度是多少？

• 你当前实现的findingDup算法时间复杂度最坏为O(n)，无法达到亚线性要求。
• 原因说明：代码中二分查找目标值索引的步骤确实是O(log n)，但后续向左右遍历统计重复次数的逻辑存在性能缺陷：如果目标值的重复次数和数组规模n同阶（比如数组一半元素都是目标值），遍历步骤的耗时会达到O(n)，你新增的全数组元素相同的判断只能覆盖最极端的全重复场景，其他高重复场景依然会导致复杂度退化。

要满足亚线性要求，你可以替换左右遍历的逻辑，通过两次二分查找分别定位目标值在有序数组中第一次出现的左边界、最后一次出现的右边界，最终重复次数为右边界索引 - 左边界索引 + 1，找不到目标值直接返回0即可，全程仅执行两次二分操作，复杂度稳定为O(log n)。

public class Controller {
    public static void main(String[] args) {
        int[] A = {-1, 2, 3, 5, 6, 6, 6, 9, 10};
        int value = 6;
        System.out.println(countDup(A, value));
    }

    // 查找目标值第一次出现的索引，不存在返回-1
    private static int findLeftBound(int[] a, int x) {
        int low = 0, high = a.length - 1;
        int res = -1;
        while (low <= high) {
            // 等价于(low+high)/2，避免整数溢出
            int mid = low + (high - low) / 2;
            if (a[mid] == x) {
                res = mid;
                // 继续向左搜索更早的匹配项
                high = mid - 1;
            } else if (a[mid] < x) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return res;
    }

    // 查找目标值最后一次出现的索引，不存在返回-1
    private static int findRightBound(int[] a, int x) {
        int low = 0, high = a.length - 1;
        int res = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (a[mid] == x) {
                res = mid;
                // 继续向右搜索更晚的匹配项
                low = mid + 1;
            } else if (a[mid] < x) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return res;
    }

    public static int countDup(int[] a, int x) {
        int left = findLeftBound(a, x);
        if (left == -1) {
            return 0;
        }
        int right = findRightBound(a, x);
        return right - left + 1;
    }
}

内容的提问来源于stack exchange，提问作者Hanser Benitez