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