怎样在排序数组中查找数字

这期内容当中小编将会给大家带来有关怎样在排序数组中查找数字，文章内容丰富且以专业的角度为大家分析和叙述，阅读完这篇文章希望大家可以有所收获。

题目:
统计一个数字在排序数组中出现的次数. 例如输入排序数组{1,2,3,3,3,3,4,5},由于3在这个数中出现了4次,输出4.

# -*- coding: utf-8 -*-# @Time         : 2019-07-13 15:10# @Author       : Jayce Wong# @ProjectName  : job# @FileName     : getNumberOfK.py# @Blog         : https://blog.51cto.com/jayce1111# @Github       : https://github.com/SysuJaycedef getFirstK(data, k):    start, end = 0, len(data) - 1    while start <= end:        mid = (start + end) >> 1        if data[mid] == k:            # 关键在于，如果mid是k，那么就判断前一个元素是不是也是k，如果是，说明这个位置不是            # 第一次出现，要在左边继续查找。否则，直接返回mid，因为是第一次出现了            if mid - 1 >= start and data[mid - 1] == k:                end = mid - 1            else:                return mid        elif data[mid] < k:            start = mid + 1        else:            end = mid - 1    return -1def getLastK(data, k):    start, end = 0, len(data) - 1    while start <= end:        mid = (start + end) >> 1        if data[mid] == k:            if mid + 1 <= end and data[mid + 1] == k:                start = mid + 1            else:                return mid        elif data[mid] < k:            start = mid + 1        else:            end = mid - 1    return -1def getNumberOfK(data, k):    """    要获取一个有序数组中某个元素出现的次数，最直观的做法就是遍历整个数组，然后统计该元素的出现次数，    这样做的时间复杂度是O(n)    但是由于这个数组是有序的，我们可以考虑利用二分查找的方法来解决这个问题。    如果我们先利用二分查找定位到了这个元素，然后再往前往后遍历，这样的话时间复杂度也还是O(n)。    但是如果我们在利用二分查找的时候，想办法定位这个元素第一次出现的下标和最后一次出现的下标。    在利用二分查找找到一个这个元素之后，判断这个元素是否是第一个，也就是对比这个元素的前一个是否也    是k，如果不是，说明这个元素就是第一个元素，否则在这个下标的左边继续查找。    对于最后一次出现的下标同理。    """    if not data:        return 0    first = getFirstK(data, k)    last = getLastK(data, k)    if first != -1 and last != -1:        return last - first + 1    else:        return 0def main():    data = [1, 2, 3, 3, 3, 3, 4, 5]    k = 3    print(getNumberOfK(data, k))if __name__ == '__main__':    main()

上述就是小编为大家分享的怎样在排序数组中查找数字了，如果刚好有类似的疑惑，不妨参照上述分析进行理解。如果想知道更多相关知识，欢迎关注行业资讯频道。