線性表採用順序存儲結構，線性表中的元素是有序排列的。
基本思路假設線性表中的元素是按升序排列的，先將待查找的區間分成兩部分，即[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，找到目標元素，查找結束。
二分查找模板
非遞歸版本
int binarySearch(int* nums, int numsSize, int target) { if (nums == NULL || numsSize <= 0) { return -1; } int low = 0, high = numsSize - 1; while (low <= high) { int mid = low + ((high - low) >> 1); if (nums[mid] == target) { return mid; } else if (nums[mid] > target) { high = mid - 1; } else if (nums[mid] < target) { low = mid + 1; } } return -1;}遞歸版本
int binarySearch(int* nums, int low, int high, int target) { if (low > right) { return -1; } int mid = low + (high - low) / 2; if (nums[mid] > target) { return binarySearch(nums, low, mid - 1, target); } else if (nums[mid] < target) { return binarySearch(nums, mid + 1, high, target); } else if (nums[mid] == target) { return mid; } }注意點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]，此時搜索區間為空，結束循環。