怎樣在排序數組中查找數字

這期內容當中小編將會給大家帶來有關怎樣在排序數組中查找數字，文章內容豐富且以專業的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

題目:
統計一個數字在排序數組中出現的次數. 例如輸入排序數組{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/SysuJayce

def 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 -1

def 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 -1

def 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 0

def main():
    data = [1, 2, 3, 3, 3, 3, 4, 5]
    k = 3
    print(getNumberOfK(data, k))

if __name__ == '__main__':
    main()

上述就是小編為大家分享的怎樣在排序數組中查找數字了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關知識，歡迎關注億速云行業資訊頻道。