二分查找(Binary Search)算法，也叫折半查找算法。
創(chuàng)新互聯(lián)主營興賓網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營網(wǎng)站建設(shè)方案,app軟件定制開發(fā),興賓h5小程序設(shè)計(jì)搭建,興賓網(wǎng)站營銷推廣歡迎興賓等地區(qū)企業(yè)咨詢
二分查找是一種非常簡單易懂的快速查找算法，其思想在生活中隨處可見，比如朋友聚會的時(shí)候愛玩的一個(gè)猜數(shù)游戲，我隨機(jī)寫一個(gè)0-100之間的數(shù)字，然后大家依次來猜，猜的過程中大家每猜一次我都會告訴大家猜大了還是猜小了，直到有人猜中為止，猜中的人會有一些懲罰措施。這個(gè)過程其實(shí)就是二分查找思想的一種體現(xiàn)。
回到實(shí)際的開發(fā)場景中，假設(shè)有10個(gè)訂單，其金額分別是：6，12，15，19，24，26，29，35，46，67。請從中找出訂單金額為15的訂單，利用二分查找的思想我們每次都與區(qū)間中間的數(shù)據(jù)進(jìn)行大小的比較以縮小查找的范圍，下面這幅圖代表了查找的過程，其中 left，right代表了待查找區(qū)間的下標(biāo)，mid表示待查找區(qū)間中間元素的下標(biāo)(如果范圍區(qū)間是偶數(shù)個(gè)導(dǎo)致中間數(shù)有兩個(gè)就選擇較小的那個(gè))
通過這個(gè)查找過程我們可以對二分查找的思想做一個(gè)匯總：二分查找針對的是一個(gè)有序的數(shù)據(jù)集合，查找思想有點(diǎn)類似分治思想。每次都通過跟區(qū)間的中間元素對比，將待查找的區(qū)間縮小為之前的一半，直到找到要查找的元素，或者區(qū)間被縮小為 0
理解了二分查找的思想后我們來分析二分查找的時(shí)間復(fù)雜度，首先我們要明確二分查找是一種非常高效的查找算法，通過分析其時(shí)間復(fù)雜度我們就可以發(fā)現(xiàn)，我們假設(shè)數(shù)據(jù)大小為n，每次查找完后數(shù)據(jù)的大小縮減為原來的一半，直到最后數(shù)據(jù)大小被縮減為1此時(shí)停止，如果我們用數(shù)據(jù)來描述其變化的規(guī)律那就是：
n，n/2，n/4，n/8，n/16，n/32，.......................，1；
可以看出來，這是一個(gè)等比數(shù)列，當(dāng)數(shù)據(jù)大小變?yōu)?時(shí)：
其中k 的值就是總共縮小的次數(shù)。而每一次縮小操作只涉及兩個(gè)數(shù)據(jù)的大小比較，所以，經(jīng)過了 k 次區(qū)間縮小操作，通過計(jì)算k的值我們可以得出二分查找的時(shí)間復(fù)雜度就是 O(logn)
這是一種非常高效的時(shí)間復(fù)雜度，有時(shí)候甚至比O(1)復(fù)雜度更高效，為什么這么說呢？因?yàn)閷τ趌og n來說即使n非常的大對應(yīng)的log n的值也會很小，之前在學(xué)習(xí)O(1)復(fù)雜度時(shí)我們講過O(1)代表的是一種常量級復(fù)雜度并不是說代碼只需要執(zhí)行一次，有時(shí)候可能要執(zhí)行100次，1000次這種常數(shù)級次數(shù)的復(fù)雜度都可以用O(1)表示，所以，常量級時(shí)間復(fù)雜度的算法有時(shí)候可能還沒有 O(logn) 的算法執(zhí)行效率高。
二分查找的實(shí)現(xiàn)方式有基于循環(huán)的實(shí)現(xiàn)方式，也有基于遞歸的方式，現(xiàn)給出這兩種方式編寫的代碼模板
1、基于循環(huán)的二分查找代碼模板
重慶分公司
重慶分公司
// 返回的是元素在數(shù)組中的下標(biāo)
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不斷去逼近我們的目標(biāo)值，相對好的情況直接在某段中間找到了目標(biāo)值，最壞的情況是不斷去逼近，最后left==right找到目標(biāo)值，當(dāng)然如果真的找不到目標(biāo)值也就是left>right的時(shí)候。
2、基于遞歸的二分查找代碼模板
public int recurBinarySearch(int[] array, int target,int left,int right) {
//terminal
if (left > right) {
return -1;
}
//process current 計(jì)算中間元素的下標(biāo)
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);
}
}
進(jìn)階：二分查找的實(shí)現(xiàn)我們可以分為兩大類情況
1，有序數(shù)列中不存在重復(fù)元素的簡單實(shí)現(xiàn)；
2：有序數(shù)列中存在重復(fù)元素的變形實(shí)現(xiàn)，
針對第一種，上面已經(jīng)給出了代碼模板，針對第二種，在實(shí)際的應(yīng)用場景中可能會出現(xiàn)如下幾種情況：
2.1、從數(shù)據(jù)序列中查找第一個(gè)值等于給定值的元素，比如在{6,12,15,19,24,26,29,29,29,67}中找第一個(gè)等于29的元素
2.2、從數(shù)據(jù)序列中查找最后一個(gè)值等于給定值的元素。還是剛剛的元素序列，找最后一個(gè)等于29的元素
2.3、從數(shù)據(jù)序列中查找第一個(gè)大于等于給定值的元素。
2.4、從數(shù)據(jù)序列中查找出最后一個(gè)值小于等于給定值的元素。
課后思考：針對這四種情況，代碼應(yīng)該如何實(shí)現(xiàn)呢？
二分查找的時(shí)間復(fù)雜度是O(log n)，其效率非常高，那是不是說所有情況下都可以使用二分查找呢？下面我們討論一下二分查找的應(yīng)用前提
1、待查找的數(shù)據(jù)序列必須有序
二分查找對這一要求比較苛刻，待查找的數(shù)據(jù)序列必須是有序的（單調(diào)遞增或者單調(diào)遞減），假如數(shù)據(jù)無序，那我們要先排序，然后二分查找，如果我們針對的是一組固定的靜態(tài)數(shù)據(jù)，也就說該數(shù)據(jù)序列不會進(jìn)行插入和刪除操作，那我們完全可以先排序然后二分查找，這樣子一次排序多次查找；但是如果數(shù)據(jù)序列本身不是固定的靜態(tài)的，可能涉及數(shù)據(jù)序列的插入和刪除操作，那我們每次查找前都需要進(jìn)行排序然后才能查找，這樣子成本非常的高。
2、數(shù)據(jù)的存儲依賴數(shù)組
待查找的數(shù)據(jù)序列需要使用數(shù)組進(jìn)存儲，也就是說依賴順序存儲結(jié)構(gòu)。那難道不能用其他的結(jié)構(gòu)來存儲待查找的數(shù)據(jù)序列嗎？比如使用鏈表來存儲，答案是不可以的，通過我們前面實(shí)現(xiàn)的二分查找的過程可知，二分查找，算法需要根據(jù)下標(biāo)，left,right,mid來訪問數(shù)據(jù)序列中的元素，數(shù)組按照下標(biāo)訪問元素的復(fù)雜度是O(1)，而鏈表訪問元素的時(shí)間復(fù)雜度是O(n)，因此如果使用鏈表來存儲數(shù)據(jù)二分查找的時(shí)間復(fù)雜度就會變得很高。
3、數(shù)據(jù)序列存在上下邊界
數(shù)據(jù)序列有上下邊界，才能找到中間點(diǎn)，這樣才能二分下去。
4、數(shù)據(jù)量太小或太大都不適合用二分查找
數(shù)據(jù)量很小的情況下，沒有必要使用二分查找，使用循環(huán)遍歷就夠了，因?yàn)橹挥性跀?shù)據(jù)量比較大的情況下二分查找才能體現(xiàn)出優(yōu)勢，不過在某些情況下即使數(shù)據(jù)量很小也建議大家使用二分查找，比如數(shù)據(jù)序列中的數(shù)據(jù)都是一些長度非常長的字符串，這些長度非常長的字符串比較起來也會非常的耗時(shí)，所以我們要盡可能的減少比較的次數(shù)，這樣反倒有助于提高性能。
那為什么數(shù)據(jù)量太大的情況下也不建議使用二分查找呢？因?yàn)槲覀兦懊鎰傊v到二分查找底層需要依賴數(shù)組存儲待查找的數(shù)據(jù)序列，而數(shù)組的特點(diǎn)是需要連續(xù)的內(nèi)存空間，比如現(xiàn)在有1G的訂單數(shù)據(jù)，如果用數(shù)組來存儲就需要1G的連續(xù)內(nèi)存，即便有2G的剩余內(nèi)存空間，如果這2G的內(nèi)存空間不連續(xù)那也無法申請到1G大小的數(shù)組空間，所以我們說數(shù)據(jù)量太大也不適合用二分查找。
字節(jié)跳動，美團(tuán)點(diǎn)評最近面試題，69. x 的平方根
class Solution {
// 求sqrt(x)即求：x=n^2 (n>0),就是我們所熟知的拋物線(y=x^2)右側(cè)，單調(diào)遞增,且有上下界,[1,x/2]
public int mySqrt(int x) {
//特殊判斷
if (x <=1) {
return x;
}
//找一個(gè)數(shù)k,k^2<=x,找一個(gè)最大的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：如果正好找到一個(gè)mid^2 = x則在while loop中就可以直接返回了，
2：如果while loop中還沒找到，就類似x=8，我們在[ 1，2，3，4 ]中去尋找，while loop中最后一次循環(huán)left == right == 3，我們只需找k^2 <=x的最大k值即可。
進(jìn)階：牛頓迭代法解決該問題！參考精選題解：https://leetcode-cn.com/problems/sqrtx/solution/er-fen-cha-zhao-niu-dun-fa-python-dai-ma-by-liweiw/方法二
同類題目：367. 有效的完全平方數(shù)
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;
}
}
字節(jié)，快手，百度最近面試題，33. 搜索旋轉(zhuǎn)排序數(shù)組
二分查找的變形題目
思考要點(diǎn)：
1：二分的條件：滿足有上下邊界，數(shù)組存儲可利用下標(biāo)獲取，單調(diào)性這塊原始數(shù)組是單調(diào)遞增的，旋轉(zhuǎn)之后雖然整體不是單調(diào)性的，但是其中有一半一定是單調(diào)遞增的。
2：要達(dá)到log n的復(fù)雜度肯定是要二分，但是并不能簡單套用二分的模板，我們需要先找到哪半部分是具備單調(diào)性的，并判斷target是否在該范圍內(nèi)，如果在則在這部分查找target，如果不在則在另外半部分查找。
class Solution {
public int search(int[] nums, int target) {
//此處left，right代表的是下標(biāo)
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;
}
}
網(wǎng)易，拼多多，今日頭條面試題，153. 尋找旋轉(zhuǎn)排序數(shù)組中的最小值
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]) {//右區(qū)間連續(xù),最小值一定在左半?yún)^(qū)間
//mid可能是最小值也可能不是，簡單二分的模板代碼寫right=mid-1;
right = mid;
}else if (nums[mid] > nums[right]) { //右邊區(qū)間不連續(xù),最小值一定在該區(qū)間內(nèi)
left = mid +1;
}
}
return nums[left];
}
}
進(jìn)階思考題：
使用二分查找，尋找一個(gè)半有序數(shù)組 [4, 5, 6, 7, 0, 1, 2] 中間無序的地方
新浪，愛奇藝，三星面試題，74. 搜索二維矩陣
解題思路：標(biāo)準(zhǔn)的二分m x n的矩陣可以看成 m x n 的有序數(shù)組
參考官方題解：https://leetcode-cn.com/problems/search-a-2d-matrix/solution/sou-suo-er-wei-ju-zhen-by-leetcode/
class Solution {
//標(biāo)準(zhǔn)的二分m x n的矩陣可以看成 m x n 的有序數(shù)組
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轉(zhuǎn)換陳二維數(shù)組中的下標(biāo)。
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;
}
}
本文由
傳智教育博學(xué)谷教研團(tuán)隊(duì)發(fā)布。如果本文對您有幫助，歡迎
關(guān)注和點(diǎn)贊；如果您有任何建議也可留言評論或私信，您的支持是我堅(jiān)持創(chuàng)作的動力。轉(zhuǎn)載請注明出處！
