BinarySearch
舉個(gè)非常簡(jiǎn)單的例子 在[0,1,2,3,4,5,6,7,8,9,10] 這個(gè)數(shù)列中找到7所在的位置友驮，最簡(jiǎn)單的做法就是遍歷數(shù)組驾锰，即復(fù)雜度為O(n)。繼續(xù)觀察以上數(shù)列的特點(diǎn) 有序 ，于是可以上二分查找买喧，優(yōu)化復(fù)雜度為O(log(n))淤毛。
再一個(gè)現(xiàn)實(shí)點(diǎn)的例子，1-100 在紙上隨機(jī)寫(xiě)一個(gè)數(shù)姓言，最少多少次能猜到就是用的二分查找的原理蔗蹋。
實(shí)際上手寫(xiě)二分并不是一件容易的事情，可能會(huì)出現(xiàn)死循環(huán)餐塘，查找不對(duì)的情況戒傻，需要根據(jù)要求對(duì)邊界進(jìn)行調(diào)整蜂筹。接下來(lái)就由簡(jiǎn)到繁嘗試下不同情況的二分寫(xiě)法。
（一）數(shù)據(jù)有序且唯一不翩、目標(biāo)值存在
如開(kāi)題中描述的數(shù)據(jù)[0,1,2,3,4,5,6,7,8,9,10]慌盯，目標(biāo)值為7的情況。首先設(shè)定查找邊界
int l = 0;
int r = 10;
根據(jù)折中的原則俱箱，定義第一次猜的位置
int mid = (l + r) >> 1; // l = 0 ,r = 10 mid = 5
5小于目標(biāo)值7狞谱，即目標(biāo)在mid的右邊禁漓，將左邊界進(jìn)行調(diào)整
l = mid + 1; // 5 + 1 = 6
再一次進(jìn)行嘗試 mid = (6 + 10) >> 1; //mid = 8
8大于目標(biāo)值7，即目標(biāo)在mid的左邊伶跷，將右邊界進(jìn)行調(diào)整
r = mid - 1; // 8 - 1 = 7
again, mid = (6 + 7) >> 1; //mid = 6
調(diào)整 l = 7叭莫； mid = 7烁试； 最終得到結(jié)果，共計(jì)4次靖诗。
完整代碼：
public int fun1(int[] array, int target) {
int l = 0;
int r = array.length - 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (array[mid] < target) {
l = mid + 1;
} else if (array[mid] > target) {
r = mid - 1;
} else {
return mid;
}
}
return l;
}
測(cè)試數(shù)據(jù)：
array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] target = 7
l = 0 r = 10 mid = 5
l = 6 r = 10 mid = 8
l = 6 r = 7 mid = 6
l = 7 r = 7 mid = 7
結(jié)果：7
（二）數(shù)據(jù)有序且唯一刊橘、目標(biāo)值不一定存在
在Java源碼中 Arrays 和 Collections 兩個(gè)類(lèi)提供了二分的工具類(lèi)悼院，采用返回-值的方式表示目標(biāo)值未找到
return -(low + 1); // key not found.
可以思考下這里為什么要+1据途？
另外還可以通過(guò) ~low的方式 有同樣的效果。
完整代碼：
public int fun1(int[] array, int target) {
int l = 0;
int r = array.length - 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (array[mid] < target) {
l = mid + 1;
} else if (array[mid] > target) {
r = mid - 1;
} else {
return mid;
}
}
return ~l;
}
測(cè)試數(shù)據(jù)：
array = [0, 1, 2, 3, 4, 6, 7, 8, 9, 10] target = 5
l = 0 r = 9 mid = 4
l = 5 r = 9 mid = 7
l = 5 r = 6 mid = 5
結(jié)果：-6
（三）數(shù)據(jù)有序且唯一位衩、目標(biāo)值不一定存在糖驴，目標(biāo)不存在時(shí)返回小于目標(biāo)值的最大值（大于目標(biāo)值的最小值思路相同，以下不舉例）
在（一）時(shí)贮缕，如果mid不是目標(biāo)時(shí)會(huì)跳過(guò)mid直接取 l = mid + 1 或者 r = mid - 1 的感昼，
但是本題條件不同，在mid不匹配目標(biāo)值時(shí)蜕琴，也是有可能作為查找的結(jié)果宵溅。
如 數(shù)據(jù)[0,1,3,4]，目標(biāo)值為2的情況雏搂。通過(guò)（一）的代碼得到結(jié)果為2畔派，實(shí)際想要的結(jié)果為1润绵。
測(cè)試數(shù)據(jù)：
array = [0, 1, 3, 4] target = 2
l = 0 r = 3 mid = 1
l = 2 r = 3 mid = 2
結(jié)果：2
很直接的想到可以改變邊界尘盼，可放寬左邊界范圍烦绳，即查詢的值小于目標(biāo)值時(shí) l = mid。
修改代碼后進(jìn)行嘗試午阵。
public int fun(int[] array, int target) {
int l = 0;
int r = array.length - 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (array[mid] < target) {
l = mid;
} else if (array[mid] > target) {
r = mid - 1;
} else {
return mid;
}
}
return l;
}
測(cè)試數(shù)據(jù)：
array = [0, 1, 3, 4] target = 2
l = 0 r = 3 mid = 1
l = 1 r = 3 mid = 2
l = 1 r = 1 mid = 1
l = 1 r = 1 mid = 1
底桂。惧眠。。暮顺。。捶码。惫恼。。汇荐。盆繁。。革娄。冕碟。。厕妖。言秸。
發(fā)現(xiàn)運(yùn)行半天出不了結(jié)果迎捺，GG死循環(huán)。通過(guò)調(diào)試發(fā)現(xiàn)l=r=1時(shí)抄沮，mid=1岖瑰，但與能夠找到目標(biāo)值不同，這并不是答案聪全，一直進(jìn)入 array[mid] < target 辅辩。接著又對(duì)代碼進(jìn)行修改娃圆，去掉循環(huán)中的等于號(hào)進(jìn)行嘗試讼呢，完美找到了想要的答案谦炬。
public int fun(int[] array, int target) {
int l = 0;
int r = array.length - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (array[mid] < target) {
l = mid;
} else if (array[mid] > target) {
r = mid - 1;
} else {
return mid;
}
}
return l;
}
測(cè)試數(shù)據(jù)：
array = [0, 1, 3, 4] target = 2
l = 0 r = 3 mid = 1
l = 1 r = 3 mid = 2
結(jié)果：1
但是键思，將數(shù)據(jù)換成[0,1,3]，目標(biāo)值仍是2吼鳞，運(yùn)行赔桌。。疾党。依舊是死循環(huán)。
測(cè)試數(shù)據(jù)：
array = [0, 1, 3] target = 2
l = 0 r = 2 mid = 1
l = 1 r = 2 mid = 1
l = 1 r = 2 mid = 1
竭钝。蜓氨。队伟。幽勒。。锈颗。击吱。遥昧。朵纷。永脓。。搅吁。谎懦。。界拦。盐类。在跳。
當(dāng)l = 1，r = 2時(shí)猫妙，mid = （ 1 + 2 ）/ 2 = 1 ，在這個(gè)條件下造成了死循環(huán)（雖然得到了結(jié)果1齐帚，但是邊界無(wú)法收斂）对妄。于是通過(guò)修改 mid = (l + r + 1) >> 1 修正邏輯
public int fun(int[] array, int target) {
int l = 0;
int r = array.length - 1;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (array[mid] < target) {
l = mid;
} else if (array[mid] > target) {
r = mid - 1;
} else {
return mid;
}
}
return l;
}
測(cè)試數(shù)據(jù)：
array = [0, 1, 3] target = 2
l = 0 r = 2 mid = 1
l = 1 r = 2 mid = 2
結(jié)果：1
假如將目標(biāo)值設(shè)為-1剪菱，即小于目標(biāo)值的最大值不存在的情況拴签，這就根據(jù)題意進(jìn)行處理。
此題完畢构灸，另一種情況目標(biāo)不存在時(shí)返回大于目標(biāo)值的最小值自己理解后對(duì)上面代碼進(jìn)行對(duì)應(yīng)調(diào)整即可岸梨。
（四）已知目標(biāo)值在一個(gè)有序列表中重復(fù)出現(xiàn)稠氮，求第一次出現(xiàn)的位置（最后一次出現(xiàn)的位置括袒、重復(fù)出現(xiàn)的次數(shù)）
在以上幾個(gè)題目中稿茉，當(dāng)array[mid]值等于目標(biāo)值時(shí)，就是最終的結(jié)果直接返回恃慧。這里因?yàn)槟繕?biāo)值有多個(gè)，將等于的邏輯合并到array[mid] > target中痢士，邏輯上等同于找到小于目標(biāo)值的最大值的位置怠蹂。
public int fun(int[] array, int target) {
int l = 0;
int r = array.length - 1;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (array[mid] < target) {
l = mid;
} else if (array[mid] >= target) {
r = mid - 1;
}
}
return l;
}
測(cè)試數(shù)據(jù)：
array = [0, 1, 3, 3, 3, 3, 3, 3, 4] target = 3
l = 0 r = 8 mid = 4
l = 0 r = 3 mid = 2
l = 0 r = 1 mid = 1
結(jié)果：1
這里的結(jié)果并不是最終結(jié)果少态，需要對(duì)array[l]和array[l+1]進(jìn)行判斷。
若重復(fù)的數(shù)值唯一（即除了目標(biāo)值其他均不重復(fù)）嫌佑，這種特殊情況可作為（三）的延伸屋摇。尋找等于（target-1）或小于（target-1）的最大值或等于（target+1）或小于（target+1）的最小值幽邓。
繼續(xù)擴(kuò)展求目標(biāo)值的個(gè)數(shù)，即求第一次出現(xiàn)和最后一次的位置的差值柒啤，不再做分析。
總結(jié)
上訴只是講了幾種常見(jiàn)的二分的寫(xiě)法妒峦，二分的前提是有序的數(shù)組，然后需要重點(diǎn)思考
- 目標(biāo)值存不存在
- 不存在時(shí)窥浪，是取前者還是后者（邊界如何收縮）
- 重復(fù)時(shí)怎么取值
- 邊界情況取值
。假颇。骨稿。
二分的思想很簡(jiǎn)單，代碼量也很少形耗，但是在文章開(kāi)頭也提到過(guò)激涤，手寫(xiě)二分真不是一件容易的事情倦踢。
