1129.md

题目：等值键。为 BinarySearch 类添加静态方法 rank()，它接受一个键和一个整型有序数组（可能存在重复键）作为参数并返回数组中小于该键的元素数量，以及一个类似的方法 count() 来返回数组中等于该键的元素的数量。

思路：

1. rank() 题目中意思， key 值是一定存在于数组中的，所以先调用二分查找找到 key 对应的序号，如果没找到则直接返回，因为有重复元素，所以需要从找到的序号往前遍历，查找所有小于 key 的元素个数。
2. count()。依旧先调用二分查找，找到 key 对应的序号。因为有重复元素，考虑利用双指针的思路，分别从找到序号的前一位和后一位开始查找和 key 相等的元素，统计个数即可。

def test1122(self, arr, key, lo, hi, dep):
    if lo > hi:
        return -1
    dep += 1
    s = ' ' * dep
    print(f'{s}lo:{lo}, hi:{hi}')
    mid = lo + (hi-lo)//2
    if key < arr[mid]:
        return self.test1122(arr, key, lo, mid-1, dep)
    elif key > arr[mid]:
        return self.test1122(arr, key, mid+1, hi, dep)
    else:
        return mid

def rank(self, key, a):
    n = len(a)
    res = self.test1122(a, key, 0, n-1, 0)
    if res <= 0:
        return 0
    cnt = 0
    for i in range(0, res):
        if a[i] < key:
            cnt += 1
    return cnt

def count(self, key, a):
    n = len(a)
    res = self.test1122(a, key, 0, n-1, 0)
    if res < 0:
        return 0
    cnt = 1
    s = res - 1
    f = res + 1
    while s >= 0 and f < n:
        hasFound = False
        if a[s] == key:
            hasFound = True
            s -= 1
            cnt += 1
        if a[f] == key:
            hasFound = True
            f += 1
            cnt += 1
        if not hasFound:
            break
    return cnt