<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Binary Search - 二分查找法（折半查找法） -------- #### 問題 在長度為$$ n $$的有序序列$$ s $$中查找元素$$ x $$的位置。 #### 解法 有序序列$$ s $$可以是升序或降序的，即從小到大或從大到小，本問題假設$$ s $$是升序的。 在長度為$$ n $$的升序序列$$ s $$中想要找出某個元素$$ x $$是否存在，在序列$$ s $$中初始化$$ low = 0 $$，$$ high = n-1 $$。 當$$ low \le high $$時，對于范圍$$ [low,high] $$，設$$ mid = \lfloor \frac{high+low}{2}\rfloor $$（向下取整），若$$ x = s[mid] $$則$$ mid $$即為所求，算法結束；若$$ x \lt s[mid] $$，則$$ x $$的位置在子范圍$$ s[0,mid-1] $$中，令$$ high = mid-1 $$；若$$ x \gt s[mid] $$，則$$ x $$的位置在子范圍$$ s[mid+1,n-1] $$中，令$$ low = mid+1 $$。對于縮小的子范圍$$ [low,high] $$，重復上述搜索操作，直到找到$$ x = s[mid] $$。若$$ low \gt high $$時仍然找不到$$ x = s[mid] $$，則序列$$ s $$中不存在$$ x $$。 例如下圖中，若$$ x = 17 = s[mid] $$，可以直接找到$$ x = s[4] $$：  若$$ x = 5 \lt s[mid] = 17 $$，則令$$ high = 3 $$之后繼續搜索：  若$$ x = 30 \gt s[mid] = 17 $$，則令$$ low = 5 $$之后繼續搜索：  對于長度為$$ n $$的序列$$ s $$，每次計算$$ mid $$的時間看作$$ O(1) $$。在最好情況下1次查找就可以找到；在最壞情況下需要$$ log_{2}n $$次才能找到$$ x $$。該算法的時間復雜度為$$ O(log_{2}n) $$。 -------- #### 源碼 [BinarySearch.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Search/BinarySearch.h) [BinarySearch.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Search/BinarySearch.cpp) #### 測試 [BinarySearchTest.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Search/BinarySearchTest.cpp)