[DSA] 二元搜尋(Binary Search)
**二元搜尋(Binary Search)**是一種在有序序列中查找特定元素的算法。這種搜索方法的效率非常高,比起使用線性搜索,在大型數據集中通常能夠大大減少所需的搜尋步驟。 以下是二元搜尋的基本步驟: 1. **初始化**:選取序列的中點作為當前的元素。 2. **比較**:將該元素與所尋找的元素進行比較。 3. **決策**: - 如果中點的元素**等於**所尋找的元素,則搜索成功,返回該位置。 - 如果所尋找的元素**小於**中點的元素,則在當前中點**之前**的子序列中繼續進行二元搜尋。 - 如果所尋找的元素**大於**中點的元素,則在當前中點**之後**的子序列中繼續進行二元搜尋。 4. **重複**:不斷地縮小搜尋範圍,直到找到該元素或範圍縮小到0。 這個方法的關鍵在於,每一次比較都使得搜索範圍減半,從而大大加快了搜索速度。 **時間複雜度**: 由於每次操作都會使搜索範圍減少一半,所以二元搜尋的時間複雜度是O(log n),其中n是序列的大小。這使得二元搜尋比線性搜尋(其時間複雜度為O(n))要快得多,特別是對於大型數據集。 **注意**: 要使用二元搜尋,前提是序列必須是有序的。如果數據不是有序的,那麼在使用二元搜尋之前,必須先對它進行排序。 總之,二元搜尋是一種高效的查找方法,適用於 有序 的數據集,特別是當數據集非常大時。 其他程式面試/Leetcode相關討論: Leetcode 是什麼?誰需要刷題?必考題有哪些 Top Interview Questions - LeetCode Leetcode刷題學習筆記 – Binary Search Tree(BST) Leetcode刷題學習筆記 – Two-Pointers Binary Search