iT邦幫忙

2023 iThome 鐵人賽

DAY 11
0
Software Development

30天快速打造Python資料結構&演算法邏輯刷爆LeetCode系列 第 11

DAY 11 「二元搜尋(Binary Search)」進入搜索領域的Python程式碼撰寫~

  • 分享至 

  • xImage
  •  

只能在已排序的數據集合中進行搜索的高效搜索~

  • 二元搜尋的時間複雜度是 O(log n)
    /images/emoticon/emoticon01.gif白話來說就是切記切記要已排序,切一半找做邊或右邊一直重複直到找到為止~~因O(log n)為非常高效的搜索算法

Step1:將數據集合按照某種規則排序,以保證數據的有序性。
Step2:確定搜索範圍的左右邊界,通常初始時為整個數據集合。
Step3:找到搜索範圍的中間元素,與目標值進行比較。
Step4:如果中間元素等於目標值,則搜索成功,返回該元素的索引。
Step5:如果中間元素大於目標值,則縮小搜索範圍為左半部分,並重複步驟3;如果中間元素小於目標值,則縮小搜索範圍為右半部分,並重複步驟3。
Step7:重複上述步驟,直到搜索範圍為空,表示目標值不在數據集合中。

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        mid_val = arr[mid]
        
        if mid_val == target:
            return mid
        elif mid_val < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

上一篇
DAY 10 「選擇排序(Selection Sort)」容易實作直觀的Python程式碼撰寫~
下一篇
DAY 12 「線性搜尋(Linear Search)」簡單直觀的Python搜索程式碼撰寫~
系列文
30天快速打造Python資料結構&演算法邏輯刷爆LeetCode30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言