二分查找(Binary Search)演算法，也叫折半查找演算法，
1.1、原理分析
二分查找是一種非常簡單易懂的快速查找演算法，其思想在生活中隨處可見，比如朋友聚會的時候愛玩的一個猜數游戲，我隨機寫一個0-100之間的數字，然后大家依次來猜，猜的程序中大家每猜一次我都會告訴大家猜大了還是猜小了，直到有人猜中為止，猜中的人會有一些懲罰措施，這個程序其實就是二分查找思想的一種體現，
回到實際的開發場景中，假設有10個訂單，其金額分別是：6，12，15，19，24，26，29，35，46，67，請從中找出訂單金額為15的訂單，利用二分查找的思想我們每次都與區間中間的資料進行大小的比較以縮小查找的范圍，下面這幅圖代表了查找的程序，其中 left，right代表了待查找區間的下標，mid表示待查找區間中間元素的下標(如果范圍區間是偶數個導致中間數有兩個就選擇較小的那個)
通過這個查找程序我們可以對二分查找的思想做一個匯總：二分查找針對的是一個有序的資料集合，查找思想有點類似分治思想，每次都通過跟區間的中間元素對比，將待查找的區間縮小為之前的一半，直到找到要查找的元素，或者區間被縮小為 0
1.2、復雜度分析
理解了二分查找的思想后我們來分析二分查找的時間復雜度，首先我們要明確二分查找是一種非常高效的查找演算法，通過分析其時間復雜度我們就可以發現，我們假設資料大小為n，每次查找完后資料的大小縮減為原來的一半，直到最后資料大小被縮減為1此時停止，如果我們用資料來描述其變化的規律那就是：
n，n/2，n/4，n/8，n/16，n/32，.......................，1；
可以看出來，這是一個等比數列，當資料大小變為1時：
其中k 的值就是總共縮小的次數，而每一次縮小操作只涉及兩個資料的大小比較，所以，經過了 k 次區間縮小操作，通過計算k的值我們可以得出二分查找的時間復雜度就是 O(logn)
這是一種非常高效的時間復雜度，有時候甚至比O(1)復雜度更高效，為什么這么說呢？因為對于log n來說即使n非常的大對應的log n的值也會很小，之前在學習O(1)復雜度時我們講過O(1)代表的是一種常量級復雜度并不是說代碼只需要執行一次，有時候可能要執行100次，1000次這種常數級次數的復雜度都可以用O(1)表示，所以，常量級時間復雜度的演算法有時候可能還沒有 O(logn) 的演算法執行效率高，
1.3、代碼實作
二分查找的實作方式有基于回圈的實作方式，也有基于遞回的方式，現給出這兩種方式撰寫的代碼模板
1、基于回圈的二分查找代碼模板
// 回傳的是元素在陣列中的下標
public int binarySearch(int[] array, int target) {
int left = 0, right = array.length - 1, mid;
while (left <= right) {
// mid = （left + right）>> 1
mid = left + ((right - left) >>1) ;
if (array[mid] == target) {
return mid;
} else if (array[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
用mid不斷去逼近我們的目標值，相對好的情況直接在某段中間找到了目標值，最壞的情況是不斷去逼近，最后left==right找到目標值，當然如果真的找不到目標值也就是left>right的時候，
2、基于遞回的二分查找代碼模板
public int recurBinarySearch(int[] array, int target,int left,int right) {
//terminal
if (left > right) {
return -1;
}
//process current 計算中間元素的下標
int mid = left + ((right - left)>>1);
if (array[mid] == target) {
return mid;
}else if (array[mid] > target) {
//drill down
return recurBinarySearch(array,target,left,mid-1);
}else {
return recurBinarySearch(array,target,mid+1,right);
}
}
進階：二分查找的實作我們可以分為兩大類情況
1，有序數列中不存在重復元素的簡單實作；
2：有序數列中存在重復元素的變形實作，
針對第一種，上面已經給出了代碼模板，針對第二種，在實際的應用場景中可能會出現如下幾種情況：
2.1、從資料序列中查找第一個值等于給定值的元素，比如在{6,12,15,19,24,26,29,29,29,67}中找第一個等于29的元素
2.2、從資料序列中查找最后一個值等于給定值的元素，還是剛剛的元素序列，找最后一個等于29的元素
2.3、從資料序列中查找第一個大于等于給定值的元素，
2.4、從資料序列中查找出最后一個值小于等于給定值的元素，
課后思考：針對這四種情況，代碼應該如何實作呢？
1.4、應用場景說明
二分查找的時間復雜度是O(log n)，其效率非常高，那是不是說所有情況下都可以使用二分查找呢？下面我們討論一下二分查找的應用前提
1、待查找的資料序列必須有序
二分查找對這一要求比較苛刻，待查找的資料序列必須是有序的（單調遞增或者單調遞減），假如資料無序，那我們要先排序，然后二分查找，如果我們針對的是一組固定的靜態資料，也就說該資料序列不會進行插入和洗掉操作，那我們完全可以先排序然后二分查找，這樣子一次排序多次查找；但是如果資料序列本身不是固定的靜態的，可能涉及資料序列的插入和洗掉操作，那我們每次查找前都需要進行排序然后才能查找，這樣子成本非常的高，
2、資料的存盤依賴陣列
待查找的資料序列需要使用陣列進存盤，也就是說依賴順序存盤結構，那難道不能用其他的結構來存盤待查找的資料序列嗎？比如使用鏈表來存盤，答案是不可以的，通過我們前面實作的二分查找的程序可知，二分查找，演算法需要根據下標，left,right,mid來訪問資料序列中的元素，陣列按照下標訪問元素的復雜度是O(1)，而鏈表訪問元素的時間復雜度是O(n)，因此如果使用鏈表來存盤資料二分查找的時間復雜度就會變得很高，
3、資料序列存在上下邊界
資料序列有上下邊界，才能找到中間點，這樣才能二分下去，
4、資料量太小或太大都不適合用二分查找
資料量很小的情況下，沒有必要使用二分查找，使用回圈遍歷就夠了，因為只有在資料量比較大的情況下二分查找才能體現出優勢，不過在某些情況下即使資料量很小也建議大家使用二分查找，比如資料序列中的資料都是一些長度非常長的字串，這些長度非常長的字串比較起來也會非常的耗時，所以我們要盡可能的減少比較的次數，這樣反倒有助于提高性能，
那為什么資料量太大的情況下也不建議使用二分查找呢？因為我們前面剛講到二分查找底層需要依賴陣列存盤待查找的資料序列，而陣列的特點是需要連續的記憶體空間，比如現在有1G的訂單資料，如果用陣列來存盤就需要1G的連續記憶體，即便有2G的剩余記憶體空間，如果這2G的記憶體空間不連續那也無法申請到1G大小的陣列空間，所以我們說資料量太大也不適合用二分查找，
2、面試實戰
69. x 的平方根
位元組跳動，美團點評最近面試題，69. x 的平方根
class Solution {
// 求sqrt(x)即求：x=n^2 (n>0),就是我們所熟知的拋物線(y=x^2)右側，單調遞增,且有上下界,[1,x/2]
public int mySqrt(int x) {
//特殊判斷
if (x <=1) {
return x;
}
//找一個數k,k^2<=x,找一個最大的k就是我們想要的
long left=1,right = x>>1,mid = 0;
while (left <=right ) {
mid = (left+right) >>1;
if (mid * mid < x) {
left = mid + 1;
}else if (mid * mid > x) {
right = mid - 1;
}else {
return (int)mid;
}
}
return (int)left-1;
}
}
代碼解釋：
1：如果正好找到一個mid^2 = x則在while loop中就可以直接回傳了，
2：如果while loop中還沒找到，就類似x=8，我們在[ 1，2，3，4 ]中去尋找，while loop中最后一次回圈left == right == 3，我們只需找k^2 <=x的最大k值即可，
進階：牛頓迭代法解決該問題！參考精選題解：https://leetcode-cn.com/problems/sqrtx/solution/er-fen-cha-zhao-niu-dun-fa-python-dai-ma-by-liweiw/方法二
同類題目：367. 有效的完全平方數
class Solution {
public boolean isPerfectSquare(int x) {
//特殊判斷
if (x <=1) {
return true;
}
long left=1,right = x>>1,mid = 0;
while (left <=right ) {
mid = (left+right) >>1;
if (mid * mid < x) {
left = mid + 1;
}else if (mid * mid > x) {
right = mid - 1;
}else {
return true;
}
}
return false;
}
}
33. 搜索旋轉排序陣列
位元組，快手，百度最近面試題，33. 搜索旋轉排序陣列
二分查找的變形題目
思考要點：
1：二分的條件：滿足有上下邊界，陣列存盤可利用下標獲取，單調性這塊原始陣列是單調遞增的，旋轉之后雖然整體不是單調性的，但是其中有一半一定是單調遞增的，
2：要達到log n的復雜度肯定是要二分，但是并不能簡單套用二分的模板，我們需要先找到哪半部分是具備單調性的，并判斷target是否在該范圍內，如果在則在這部分查找target，如果不在則在另外半部分查找，
class Solution {
public int search(int[] nums, int target) {
//此處left，right代表的是下標
int left=0,right = nums.length-1,mid=0;
while (left <= right) {
mid = (left+right) >>1;
if (nums[mid] == target) {
return mid;
}
//前半部分有序
if (nums[left] <= nums[mid]) {
//target如果在前半部分則在前半部分找,否則在后半部分找
if (target < nums[mid] && target >=nums[left] ) {
right = mid -1;
}else {
left = mid + 1;
}
}else {
//后半部分有序
//target如果在后半部分則在后半部分找，否則在前半部分找
if (target > nums[mid] && target <= nums[right]) {
left = mid +1;
}else {
right = mid -1;
}
}
}
return -1;
}
}
153. 尋找旋轉排序陣列中的最小值
網易，拼多多，今日頭條面試題，153. 尋找旋轉排序陣列中的最小值
class Solution {
//二分,但不能套用簡單的二分模板,修改二分的判斷條件
public int findMin(int[] nums) {
int left=0,right=nums.length-1,mid = 0;
/*
在這里如果left==right則可以直接回傳了,最小元素一定是它
*/
while (left < right ) {
mid = (left + right) >>1;
if (nums[mid] < nums[right]) {//右區間連續,最小值一定在左半區間
//mid可能是最小值也可能不是，簡單二分的模板代碼寫right=mid-1;
right = mid;
}else if (nums[mid] > nums[right]) { //右邊區間不連續,最小值一定在該區間內
left = mid +1;
}
}
return nums[left];
}
}
進階思考題：
使用二分查找，尋找一個半有序陣列 [4, 5, 6, 7, 0, 1, 2] 中間無序的地方
74. 搜索二維矩陣
新浪，愛奇藝，三星面試題，74. 搜索二維矩陣
解題思路：標準的二分m x n的矩陣可以看成 m x n 的有序陣列
參考官方題解：https://leetcode-cn.com/problems/search-a-2d-matrix/solution/sou-suo-er-wei-ju-zhen-by-leetcode/
class Solution {
//標準的二分m x n的矩陣可以看成 m x n 的有序陣列
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
if (m ==0) {
return false;
}
int n = matrix[0].length;
int left = 0;
int right = m * n -1;
int mid=0,row=0,col=0;
while (left<=right) {
mid = (left+right)>>1;
//最重要的就是將mid轉換陳二維陣列中的下標，
row = mid / n;
col = mid % n;
if (matrix[row][col] == target) {
return true;
}else if (matrix[row][col] < target) {
left = mid +1;
}else {
right = mid-1;
}
}
return false;
}
}
本文由
傳智教育博學谷教研團隊發布，如果本文對您有幫助，歡迎
關注和點贊；如果您有任何建議也可留言評論或私信，您的支持是我堅持創作的動力，轉載請注明出處！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/531398.html
標籤：Java
上一篇：String常用API