二分查找 - 基礎(chǔ)篇
前言
從一個(gè)有序的數(shù)組中，找到某元素的值，通常思路就是二分查找。二分查找是一個(gè)常考的知識(shí)點(diǎn)。同時(shí)，它也是非常容易出錯(cuò)的一道面試題。左右指針的位置，取值，比較是大于還是大于等于。里面細(xì)節(jié)很多。死記硬背往往容易出錯(cuò)，只有真正理解思路和多多練習(xí)，才能掌握不出錯(cuò)的”二分算法“。
本篇文章是二分查找的入門(mén)篇。將會(huì)介紹最傳統(tǒng)，最容易理解與書(shū)寫(xiě)的二分算法。并介紹四種二分查找的進(jìn)階問(wèn)題。在理解本文的基礎(chǔ)上，后續(xù)文章將會(huì)再分享二分的各種變形和其他模板。
原題：在有序數(shù)組中查找定值
思路很簡(jiǎn)單，利用數(shù)組有序的特性，每次將數(shù)組二分，拿中間元素和目標(biāo)值比較。中間元素和目標(biāo)值相等，直接返回下標(biāo)索引。中間元素比目標(biāo)值小，則去右區(qū)間繼續(xù)二分查找，否則去左區(qū)間二分查找。
代碼如下，并不復(fù)雜，但有幾個(gè)需要注意的細(xì)節(jié)：
-
循環(huán)條件
比較大小使用 <= 小于等于號(hào)
-
防止死循環(huán)
更新low，high指針?lè)謩e取值mid + 1 和 mid -1，注意這里的+1 和 -1，可以讓我們不用考慮死循環(huán)以及左中點(diǎn)，右中點(diǎn)情況。假如我們使用
high = mid，當(dāng)low = high的時(shí)候，就有可能進(jìn)入high = mid的分支邏輯中，導(dǎo)致無(wú)限死循環(huán)。 -
注意溢出
在取中間值時(shí)，很多人常用
mid = (left + right) / 2的形式，當(dāng)left與right數(shù)值的加和較大時(shí) ，是有可能溢出Int的取值范圍的?？梢圆捎?code>mid = left + (right - left) / 2的形式，結(jié)果是相同的。在JDK1.8中，采用(low + high) >>> 1，>>>是無(wú)符號(hào)右移，高位自動(dòng)補(bǔ)0，所以當(dāng)low + high溢出時(shí)變成負(fù)數(shù)，無(wú)符號(hào)右移一位又變成了正數(shù)。
public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
if (a[mid] == value) {
return mid;
} else if (a[mid] < value) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
變形一：查找第一個(gè)等于給定值的元素
與原題區(qū)別在于，當(dāng)a[mid] == value時(shí)，還需要確認(rèn)是不是第一個(gè)值等于給定值的元素。
當(dāng)遍歷到數(shù)組第一個(gè)數(shù)，或者左邊值不同時(shí)，必定是第一個(gè)，直接返回（此處同時(shí)做了溢出校驗(yàn)）
當(dāng)不是第一個(gè)元素時(shí)，從右到左收縮區(qū)間，繼續(xù)二分查找。
/**
* 變形一：
* 存在重復(fù)元素，查找第一個(gè)等于給定值的元素
*/
public int bsearch1(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
if (a[mid] > value) {
high = mid - 1;
} else if (a[mid] < value) {
low = mid + 1;
} else {
//此處區(qū)別在于，當(dāng)a[mid]等于需要的值時(shí)，還需要確認(rèn)是不是第一個(gè)值等于給定值的元素.當(dāng)遍歷到數(shù)組第一個(gè)數(shù)，或者左邊值不同時(shí)，必定是第一個(gè)，直接返回
if ((mid == 0) || (a[mid - 1] != value)) {
return mid;
} else {
high = mid - 1;
}
}
}
return -1;
}
變形二：查找最后一個(gè)等于給定值的元素
類(lèi)比變形一，變形一查找的第一個(gè)，此處查找的最后一個(gè)元素。即需要確認(rèn)是不是最后一個(gè)值等于給定值的元素。
當(dāng)遍歷到數(shù)組最后一位，或者右邊元素值不等時(shí)，必定是最后一個(gè)，返回下標(biāo)。
如果不是最后一個(gè)元素，從左到右收縮區(qū)間，繼續(xù)二分查找。
/**
* 變形二：
* 查找最后一個(gè)值等于給定值的元素
*/
public int bsearch2(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
if (a[mid] > value) {
high = mid - 1;
} else if (a[mid] < value) {
low = mid + 1;
} else {
//此處區(qū)別在于，當(dāng)a[mid]等于需要的值時(shí)，還需要確認(rèn)是不是最后一個(gè)值等于給定值的元素.當(dāng)遍歷到數(shù)組最后一位，或者右邊值不同時(shí)，符合要求直接返回
if ((mid == n - 1) || (a[mid + 1] != value)) {
return mid;
} else {
low = mid + 1;
}
}
}
return -1;
}
變形三：查找第一個(gè)大于等于給定值的元素
在變形一基礎(chǔ)上，將條件從查找一個(gè)等于定值的元素 改成 第一個(gè)大于等于定值的元素，增加了一個(gè)大于的判斷條件。則代碼如下：
/**，
* 變形三：
* 查找第一個(gè)大于等于給定值的元素
* 如序列：3，4，6，7，19 查找第一個(gè)大于5的元素，即為6
* 第一個(gè)大于給定值，則說(shuō)明上一個(gè)小于給定值，依次判斷
*/
public int bsearch3(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
if (a[mid] >= value) {
if ((mid == 0) || (a[mid - 1] < value)) {
return mid;
} else {
high = mid - 1;
}
} else {
low = mid + 1;
}
}
return -1;
}
變形四：查找最后一個(gè)小于等于給定值的元素
類(lèi)比上面三題，此處不再贅述。
/**
* 變形四：
* 查找最后一個(gè)小于等于給定值的元素、
* 如：3，5，6，8，9，10 最后一個(gè)小于7的元素是6
*/
public int bsearch4(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
if (a[mid] > value) {
high = mid - 1;
} else {
if ((mid == n - 1) || (a[mid + 1] > value)) {
return mid;
} else {
low = mid + 1;
}
}
}
return -1;
}
