53Ⅰ.在排序数组中查找数字

raylan.chen大约 2 分钟

先查找 scores[mid] == target，随后再循环遍历 mid 左右两边可能出现 scores[i-- / j++] == target 的情况

例如：

[2,2,3,4,4,4,5,6,6,8], target = 4

class Solution {
    public int countTarget(int[] scores, int target) {
        if (scores == null || scores.length == 0) return 0;
        int len = scores.length - 1;
        int left = 0;
        int right = len;
        int cou = 0;
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;

            if (scores[mid] == target) {
                int tmp = mid;                
                while (tmp >= left && target == scores[tmp--]) cou++;
                tmp = mid + 1;
                while (tmp <= right && target == scores[tmp++]) cou++;
                break;
            }

            if (scores[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return cou;
    }
}

优秀题解

class Solution {
    public int countTarget(int[] scores, int target) {
        return helper(scores, target) - helper(scores, target - 1);
    }
    int helper(int[] scores, int tar) {
        int i = 0, j = scores.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            // scores[mid] 遇到『小于 以及 等于 target』，i 都要 + 1
            if(scores[m] <= tar) i = m + 1;
            else j = m - 1;
        }
        return i;
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/solutions/155893/mian-shi-ti-53-i-zai-pai-xu-shu-zu-zhong-cha-zha-5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

使用两次二分查找，

第一次二分查找，寻找第一个大于 target 的元素 ? (这里不太确定自己的判断)

第一次二分查找，寻找第一个大于 target - 1 的元素 ?

然后两次二分查找的结果相减

53Ⅰ.在排序数组中查找数字

53Ⅰ.在排序数组中查找数字

参考链接

个人尝试

优秀题解