二分查找算法总结
二分查找有N多種寫法，有各種各樣的形式，選一種合適自己，自己能夠理解記住的才是最好的。
對于最最最原始的二分查找，即給出一個Key，查找出key值的索引號。?
最經典的二分查找對返回來的索引號沒有任何要求，只要其對應的值是Key就可以了！！！！
使用二分查找算法的序列必須是有序序列
核心代碼：
int binarySearch(int a[],int key,int left,int right)
{
? ? ?while(left+1 < right)
? ? {
? ? ? ? int mid=(left+right)/2;
? ? ? ? if (a[mid]==key) {return mid;}
? ? ? ? else if (a[mid]<key)
? ? ? ? ?{
? ? ? ? ? ? ? left=mid;
? ? ? ? ?}
? ? ? ? else {
? ? ? ? ? ? ? right=mid;
? ? ? ? ? ? ?}
? ? }
? ? ?if ( a[left]==key) return left;
? ? ?if ( a[right]==key) return right;
? ? ?return -1;
}
很多版本不同的地方其實就是在于while循環條件的判斷和left(low、l)、right(high、hi)和mid的關系。
比較常見的有：
int binarySearch(int a[],int key,int left,int right)
{
? ? ?while(left<=right)
? ? {
? ? ? ? int mid=(left+right)/2;
? ? ? ? if (a[mid]==key) {return mid;}
? ? ? ? else if (a[mid]<key)
? ? ? ? ?{
? ? ? ? ? ? ? left=mid+1;
? ? ? ? ?}
? ? ? ? else {
? ? ? ? ? ? ? right=mid-1;
? ? ? ? ? ? ?}
? ? }
? ? ?return -1;
}
其實！！！這里while循環里面是什么取決于left、right是怎么移動的。
如果是：?
left=mid+1?
right=mid-1?
那么最后停止的條件就是應該是left>right。也就是說循環的條件應該是left<=right。
如果是?
left=mid?
right=mid?
那么停止的條件就是left+1>right。因為在這種情況下，當循環到right-left=1時（兩個指針差相鄰），兩者再計算mid時就永遠保持一樣的right和left了。
經典的二分查找了解了，下面就是二分查找的各種“變形”
1.如果序列存在重復的Key值，返回Key值的最小下標，不存在則返回-1。
其實，對于這個問題（包括下面的這些問題），處理點都只是在一個地方，把握好這個地方后所有問題都可以迎刃而解！！！
首先，這個問題不同于經典二分查找的地方在于，在經典二分查找中，我們一旦找到
if (a[mid]==key) {
? ? return mid;
}
我們就return 了，也就是說程序就結束了！！！?
但是現在的問題是key在序列中有重復的，也就是說我們需要繼續找，不能停止！！！
我們再來對比經典二分查找還需要改變什么：所謂二分查找核心其實就是：
? ? ? ? ?if (a[mid]<key)
? ? ? ? ?{
? ? ? ? ? ? ? left=mid;
? ? ? ? ?}
? ? ? ? else {
? ? ? ? ? ? ? right=mid;
? ? ? ? ? ? ?}
這個是核心，這個不能變。?
上面提到既然找到一個key值后不能return ，
那 a[mid]==key 應該放在哪判斷？？
也就是說等號放哪。等號是跟著 a[mid]< key，還是a[mid]>key？？？
結論：
如果是a[mid]<=key里的時候是找最大的下標。
如果是a[mid]>=key里的時候是找最小的下標。
?
具體看代碼：?
下面這個是把=號（a[mid]==key)放在了a[mid]> key里。所以實現的是找最小的下標。
int binarySearch(int a[],int key,int left,int right)
{
? ? ?while(left+1 < right)
? ? {
? ? ? ? int mid=(left+right)/2;
? ? ? ? if (a[mid]<key)
? ? ? ? ?{
? ? ? ? ? ? ? left=mid;
? ? ? ? ?}
? ? ? ? else {
? ? ? ? ? ? ? right=mid;
? ? ? ? ? ? ?}
? ? }
? ? ?if (a[left]==key) return left;
? ? ?if (a[right]==key) return right;
? ? ?return -1;
}
這是為什么呢？其實理由很好理解，越大的下標值越靠后，而當我們碰到a[mid]==key時說明我們找到一個key值，但是不確定是不是最后一個，所以我們需要做的是在這個key之后的值中尋找，也就是把left指針移后來。?
同理，當我們希望得到最小下標值時，就需要把right指針移到左邊來。這樣才能不斷往小下標靠攏。?
那沒碰到a[mid]==key時怎么辦？？按照二分查找的思路繼續走。
另外，我們需要有一個認識：二分查找最后的結果往往是把key值落在left和right指針所在的區間里，下面舉個例子：
比如對于數組a[8]={1,2,5,7,9,12,14,15}，查找8時，用上面的移動方法(left=mid,right=mid,而不是left=mid-1,right=mid-1)。我們可以得到在結束while循環時，left一定是指在7處，right一定是指在9處。
再比如a[8]={1,2,5,7,9,12,14,15}，查找2時，left和right指在哪？可以肯定的是只有兩種情況：left->1 right->2 或者left->2 right->5。?
到底是哪一種，取決于a[mid]==key放在哪處。?
根據前面的，當是：
? ? ? ? if (a[mid]<=key)
? ? ? ? ?{
? ? ? ? ? ? ? left=mid;
? ? ? ? ?}
? ? ? ? else {
? ? ? ? ? ? ? right=mid;
? ? ? ? ? ? ?}
一定是：left->2 right->5?
當是：
? ? ? ? if (a[mid]<key)
? ? ? ? ?{
? ? ? ? ? ? ? left=mid;
? ? ? ? ?}
? ? ? ? else {
? ? ? ? ? ? ? right=mid;
? ? ? ? ? ? ?}
一定是 left->1 right->2。?
對于查找2時有兩種情況，而8只有一種情況正是由于a[mid]==key引起的不同。
當然，如果查找一個比數組最小值還小的值，比如對于 a[8]={1,2,5,7,9,12,14,15}找-1,最后left,right分別指在1,2。如果是找100，left->14 right->15。
2.如果序列存在重復的Key值，返回Key值的最大下標，不存在返回-1。
int binarySearch(int a[],int key,int left,int right)
{
? ? ?while(left+1 < right)
? ? {
? ? ? ? int mid=(left+right)/2;
? ? ? ? if (a[mid]<=key)
? ? ? ? ?{
? ? ? ? ? ? ? left=mid;
? ? ? ? ?}
? ? ? ? else {
? ? ? ? ? ? ? right=mid;
? ? ? ? ? ? ?}
? ? ? ?}
? ? ?if (a[right]==key) return right;
? ? ?if (a[left]==key) return left;
? ? ?return -1;
}
特別需要注意的是，在得到left和right后在單獨處理。注意right和left返回的次序。
3.返回大于Key值的最小下標。
這句話剛開始讀了幾次也沒讀明白，其實就是比如有?
a[8]={1,2,5,7,9,12,14,15}。希望返回大于7的最小下標，也就說說返回9的下標4。?
其實這個問題很好解決，我們只要返回7的最大下標然后+1就可以。?
具體來說用上面2的算法。?
這里需要注意的是！！！！ 我們用的是：返回7最大下標的算法去獲得大于7最小的下標。
int binarySearch(int a[],int key,int left,int right)
{
? ? ?while(left+1 < right)
? ? {
? ? ? ? int mid=(left+right)/2;
? ? ? ? if (a[mid]<=key)
? ? ? ? ?{
? ? ? ? ? ? ? left=mid;
? ? ? ? ?}
? ? ? ? else {
? ? ? ? ? ? ? right=mid;
? ? ? ? ? ? ?}
? ? ? ?}
? ? ?if (a[left]>key) return left;//考慮到比數組里最小的還小
? ? ?if (a[right]>key) return right;
? ? ?return -1;
}
4.返回小于Key值的最大下標。
同樣沿用3的思路。
5.返回大于等于Key值的最小下標。
這里單獨把“等于”從4里面拿出來是因為循環結束需要單獨處理的部分不太一樣。
int binarySearch(int a[],int key,int left,int right)
{
? ? ?while(left+1 < right)
? ? {
? ? ? ? int mid=(left+right)/2;
? ? ? ? if (a[mid]<=key)
? ? ? ? ?{
? ? ? ? ? ? ? left=mid;
? ? ? ? ?}
? ? ? ? else {
? ? ? ? ? ? ? right=mid;
? ? ? ? ? ? ?}
? ? ? ?}
? ? ?if (a[left]>=key) return left;
? ? ?if (a[right]>=key) return right;
? ? ?return -1;
}
6.返回小于等于Key值的最大下標。
與5類似。
總結-1
其實不管是哪一種情況，也不管是什么樣新的需求。把經典的二分查找弄明白后，其他的地方都是很好理解。特別就是注意到上面已經提到過的一個東西：?
二分查找（left=mid,right=mid，這種更新方式）完之后left和right都是指在包含key的區間處的（當然這里不考慮比數組最小的還小和比數組最大的還大的兩種情況。其余情況key總是落在left和right所指的值之間）。特別需要單獨考慮的就是key值在序列里存在時有兩種可能的情況，這個需要根據需求進一步來確定是哪一種。
除了經典的情況，數組{1,2,5,7,9,12,14,15}:?
得到大于8的最小下標值，最終：left->7,right->9?
得到小于8的最大下標值，最終: left->7,right->9
得到大于5的最小下標值，最終：left->5,right->7?
得到小于5的最大下標值，最終: left->2,right->5
數組{1,2,5,7,9,9,9,9,9,9,9,12,14,15}:?
得到等于9的最小下標值，最終：left->7,right->9?
得到等于9的最大下標值，最終: left->9,right->12
二分查找復雜度
時間復雜度是O(logn)。?
證明很容易,每次折半，假設有n個元素n,n/2,n/4…..n/2^k。假設最壞的時候折半了k次時當只剩一個元素，則有n/2^k=1 ===>k=log(n)
空間復雜度：?
遞歸空間復雜度=遞歸的深度×輔助空間的大小?
二分查找遞歸時輔助空間為常數，遞歸深度了log(n)，所以空間復雜度log(n)
非遞歸的情況下：?
二分查找的空間復雜度為常數O(1)
?
總結
- 上一篇： Java集合：HashMap
- 下一篇： 多线程：happens-before 先