二分查找又稱折半查找（Binary Search），是一種效率較高的查找方法。前提
線性表采用順序存儲結構，線性表中的元素是有序排列的。
基本思路
假設線性表中的元素是按升序排列的，先将待查找的區間分成兩部分，即[low, mid) 和 (mid, high] ，查找過程從線性表的中間元素開始，如果中間元素恰好是要查找的元素，則結束查找；如果中間元素大于要查找的元素，則在前半區間 [low, mid) 中查找；否則就在後半區間(mid, high] 中查找；而且跟開始一樣先從中間元素開始比較，直到找到要查找的元素或者線性表中不存在該元素（查找區間最後為空）。
舉栗
給定一個有序數組：[0, 5, 6, 9, 12, 15, 18, 20, 23]，查找target：6
查找過程如下：
由于nums[mid] = 12 > target = 6, 則到mid的前半區間[low, mid)中查找，high = mid - 1 = 3，mid = (low + high) / 2 = 1。
此時nums[mid] = 5 < target = 6，則到mid的後半區間(mid, high] 中查找，low = mid + 1 = 2, mid = (low + high) / 2 = 2。
這時nums[mid] = 6 == target = 6，找到目标元素，查找結束。
二分查找模闆
非遞歸版本
遞歸版本
mid 為何取 low + ((high - low) >> 1) 或者 low + (high - low) / 2 而不是 (high + low) / 2 ？
因為 int 類型最大表示範圍是 2147483647 ，那麼對于兩個都接近 2147483647 的數字而言，它們相加的結果将會溢出，變成負數。是以為了避免出現整數溢出的風險，使用前面兩個替代。
while 循環何時終止？
當搜尋區間為空或者目标元素找到，就結束循環。
while (low <= high) 終止條件是 low == high + 1 ，即[high + 1, high]，此時搜尋區間為空，結束循環。