二分查找演算法詳解
前言
最近刷了很多二分查找相關的題目，這裡將近期的收穫做一個總結，包括二分查找的變形問題。如果能掌握，我相信以後基本上二分查找相關的問題對你來說，都不是問題。
二分查找的效率
二分查找是啥我想不用過多的說明。我們都知道二分查找的時間複雜程度是O(logN)。
O(logn) 查找速度有多快呢？我們來分析一下。
我們假設數據大小是 n，每次查找後數據都會縮小為原來的一半，也就是會除以 2。最壞情況下，直到查找區間被縮小為空，才停止。
就因為這種特性，有的時候甚至比時間複雜度是常量級 O(1) 的演算法還要高效。為什麼這麼說呢？
因為 logn 是一個非常「恐怖」的數量級，即便 n 非常非常大，對應的 logn 也很小。比如 n 等於 2 的 32 次方，這個數很大了吧？大約是 42 億。也就是說，如果我們在 42 億個數據中用二分查找一個數據，最多需要比較 32 次。
簡單的二分查找
簡單的二分查找我想大家應該都寫過。但是想一次將二分查找寫對估計10個人裡面只有1個人能做到。下面給出題目和程式碼，我們具體來分析一下。
題目：在有序的數組a里，找到某個指定的數據value。
public int bsearch(int[] a, int value) {
int low = 0;
int high = a.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == value) {
return mid;
} else if (a[mid] < value) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
上訴程式碼可以作為一個二分查找的模板程式碼，我相信你能輕易的看懂這段程式碼。這裡需要強調幾個容易出錯的地方：
1.循環退出條件：
注意是low<=high，而不是 low
2.mid 的取值：
實際上，mid=(low+high)/2 這種寫法是有問題的。因為如果 low 和 high 比較大的話，兩者之和就有可能會溢出。改進的方法是將 mid 的計算方式寫成low+(high-low)/2。更進一步，如果要將性能優化到極致的話，我們可以將這裡的除以 2 操作轉化成位運算 low+((high-low)>>1)。因為相比除法運算來說，電腦處理位運算要快得多。
3.low 和 high 的更新
low=mid+1，high=mid-1。注意這裡的 +1 和 -1，如果直接寫成 low=mid 或者 high=mid，就可能會發生死循環。比如，當 high=3，low=3 時，如果 a[3]不等於 value，就會導致一直循環不退出。
二分查找的變形
上面這種簡單的二分查找大家基本上都會寫，需要注意的就是幾個容易出錯的地方。爭取這種簡單的二分查找都是一次性通過。
我們平常很少會寫這種簡單的二分查找，這裡我給出幾種常見的變形的二分查找演算法。我們來觀察其通用性，掌握其技巧。
1. 題目：查找第一個值等於給定值的元素
例子：a:[1,3,4,5,6,,6,6,7,8],value:6。那麼需要定位到下標為4的元素
public int bsearch(int[] a, int value) {
int low = 0;
int high = a.length - 1 - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else if (a[mid] < value) {
low = mid + 1;
} else {
if ((mid == 0) || (a[mid - 1] != value)) return mid;
else high = mid - 1;
}
}
return -1;
}
仔細看看上訴演算法中，與之前的簡單的二分查區別在哪裡？
我們來分析一下。首先我們還是按照簡單的二分查找來算。當找到指定值的時候我們不能直接放回結果。需要再判斷一下，左邊的元素與自身是否相同。不相同則返回結果。否則繼續二分。
2. 題目：查找第一個大於等於給定值的元素
例子：a:[3,4,6,7,10] 如果查找第一個大於等於5的元素，那就是6
public int bsearch(int[] a, int value) {
int low = 0;
int high = a.length - 1 - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] >= value) {
if ((mid == 0) || (a[mid - 1] < value)) return mid;
else high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
如果 a[mid]小於要查找的值 value，那要查找的值肯定在[mid+1, high]之間，所以，我們更新 low=mid+1。
對於 a[mid]大於等於給定值 value 的情況，我們要先看下這個 a[mid]是不是我們要找的第一個值大於等於給定值的元素。
如果 a[mid]前面已經沒有元素，或者前面一個元素小於要查找的值 value，那 a[mid]就是我們要找的元素。這段邏輯對應的程式碼是第 7 行。
如果 a[mid-1]也大於等於要查找的值 value，那說明要查找的元素在[low, mid-1]之間，所以，我們將 high 更新為 mid-1。
總結
要想寫好二分查找，首先我們必須保證充分理解最簡單的二分查找演算法。不熟悉的話多寫幾遍。
當遇到變形的二分查找。我們需要改動簡單的二分查找程式碼。改動的點就在a[mid]與value的對比上加上相應的條件。
上面的兩道變形的演算法如果你多做幾遍一定會有自己的體會。
最後，需要特別主義的還是那三個特別容易出錯的地方：
1.循環退出條件：
2.mid 的取值：
3.low 和 high 的更新
