前言科普

第一篇二分搜索論文是 1946 年發表，然而第一個沒有 bug 的二分查找法卻是在 1962 年才出現，中間用了 16 年的時間。

2019 年的你，在面試的過程中能手寫出沒有 bug 的二分查找法麼？

定義

在計算機科學中，二分查找（英語：binary search），也稱折半搜索（英語：half-interval search）、對數搜索（英語：logarithmic search），是一種在有序數組中查找某一特定元素的搜索算法。

搜索過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結束；

如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。

如果在某一步驟數組為空，則代表找不到。

這種搜索算法每一次比較都使搜索範圍縮小一半。

二分查找法代碼

按照上面的定義，我們來嘗試寫一下二分查找法的代碼。

public static int binary(int[] arr, int data) {
 int min = 0;
 int max = arr.length - 1;
 int mid;
 while (min <= max) {
 mid = (min + max) / 2;
 if (arr[mid] > data) {
 max = mid - 1;
 } else if (arr[mid] < data) {
 min = mid + 1;
 } else {
 return mid;
 }
 }
 return -1;
 }

現在問你，上面的代碼有沒有問題？哪段代碼會出現 bug ？

請思考一分鐘後再往下查看。

對於上面這段代碼而言，問題出在第 6 行代碼處：

mid = (min + max) / 2;

這句代碼在 min 和 max 很大的時候，會出現溢出的情況，從而導致數組訪問出錯。

別看現在輕描淡寫的指出了這個錯誤，但這個錯誤在當時可是存在了好些年。

那怎麼改進呢？一般的做法是這樣的：將加法變成減法。

public static int binary(int[] arr, int data) {
 int min = 0;
 int max = arr.length - 1;
 int mid;
 while (min <= max) {
 // 防止溢出
 mid = min + (max - min) / 2;
 if (arr[mid] > data) {
 max = mid - 1;
 } else if (arr[mid] < data) {
 min = mid + 1;
 } else {
 return mid;
 }
 }
 return -1;
 }

還有一種更高逼格的寫法，也是官方的二分搜索法的實現寫法：使用 位運算。

 public static int binary(int[] arr, int data) {
 int min = 0;
 int max = arr.length - 1;
 int mid;
 while (min <= max) {
 // 無符號位運算符的優先級較低，先括起來
 mid = min + ((max - min) >>> 1);
 if (arr[mid] > data) {
 max = mid - 1; 

 } else if (arr[mid] < data) {
 min = mid + 1;
 } else {
 return mid;
 }
 }
 return -1;
 }