前言
最近刷了很多二分查找相關的題目，這里將近期的識訓做一個總結，包括二分查找的變形問題，如果能掌握，我相信以后基本上二分查找相關的問題對你來說，都不是問題，
二分查找的效率
二分查找是啥我想不用過多的說明，我們都知道二分查找的時間復雜程度是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 的更新
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/200498.html
標籤：其他
上一篇：VM共享檔案夾設定