BinarySearch
舉個非常簡單的例子 在[0,1,2,3,4,5,6,7,8,9,10] 這個數(shù)列中找到7所在的位置，最簡單的做法就是遍歷數(shù)組，即復(fù)雜度為O(n)。繼續(xù)觀察以上數(shù)列的特點 有序 ，于是可以上二分查找，優(yōu)化復(fù)雜度為O(log(n))。
再一個現(xiàn)實點的例子，1-100 在紙上隨機寫一個數(shù)，最少多少次能猜到就是用的二分查找的原理。
實際上手寫二分并不是一件容易的事情，可能會出現(xiàn)死循環(huán)，查找不對的情況，需要根據(jù)要求對邊界進行調(diào)整。接下來就由簡到繁嘗試下不同情況的二分寫法。
（一）數(shù)據(jù)有序且唯一、目標(biāo)值存在
如開題中描述的數(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的右邊，將左邊界進行調(diào)整
l = mid + 1; // 5 + 1 = 6
再一次進行嘗試 mid = (6 + 10) >> 1; //mid = 8
8大于目標(biāo)值7，即目標(biāo)在mid的左邊，將右邊界進行調(diào)整
r = mid - 1; // 8 - 1 = 7
again, mid = (6 + 7) >> 1; //mid = 6
調(diào)整 l = 7； mid = 7； 最終得到結(jié)果，共計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;
}
測試數(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 兩個類提供了二分的工具類，采用返回-值的方式表示目標(biāo)值未找到
return -(low + 1); // key not found.
可以思考下這里為什么要+1？
另外還可以通過 ~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;
}
測試數(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)不存在時返回小于目標(biāo)值的最大值（大于目標(biāo)值的最小值思路相同，以下不舉例）
在（一）時，如果mid不是目標(biāo)時會跳過mid直接取 l = mid + 1 或者 r = mid - 1 的，
但是本題條件不同，在mid不匹配目標(biāo)值時，也是有可能作為查找的結(jié)果。
如 數(shù)據(jù)[0,1,3,4]，目標(biāo)值為2的情況。通過（一）的代碼得到結(jié)果為2，實際想要的結(jié)果為1。
測試數(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)值時 l = mid。
修改代碼后進行嘗試。
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;
}
測試數(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)運行半天出不了結(jié)果，GG死循環(huán)。通過調(diào)試發(fā)現(xiàn)l=r=1時，mid=1，但與能夠找到目標(biāo)值不同，這并不是答案，一直進入 array[mid] < target 。接著又對代碼進行修改，去掉循環(huá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;
}
測試數(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，運行。。。依舊是死循環(huán)。
測試數(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時，mid = （ 1 + 2 ）/ 2 = 1 ，在這個條件下造成了死循環(huán)（雖然得到了結(jié)果1，但是邊界無法收斂）。于是通過修改 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;
}
測試數(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ù)題意進行處理。
此題完畢，另一種情況目標(biāo)不存在時返回大于目標(biāo)值的最小值自己理解后對上面代碼進行對應(yīng)調(diào)整即可。
（四）已知目標(biāo)值在一個有序列表中重復(fù)出現(xiàn)，求第一次出現(xiàn)的位置（最后一次出現(xiàn)的位置、重復(fù)出現(xiàn)的次數(shù)）
在以上幾個題目中，當(dāng)array[mid]值等于目標(biāo)值時，就是最終的結(jié)果直接返回。這里因為目標(biāo)值有多個，將等于的邏輯合并到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;
}
測試數(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é)果，需要對array[l]和array[l+1]進行判斷。
若重復(fù)的數(shù)值唯一（即除了目標(biāo)值其他均不重復(fù)），這種特殊情況可作為（三）的延伸。尋找等于（target-1）或小于（target-1）的最大值或等于（target+1）或小于（target+1）的最小值。
繼續(xù)擴展求目標(biāo)值的個數(shù)，即求第一次出現(xiàn)和最后一次的位置的差值，不再做分析。
總結(jié)
上訴只是講了幾種常見的二分的寫法，二分的前提是有序的數(shù)組，然后需要重點思考
- 目標(biāo)值存不存在
- 不存在時，是取前者還是后者（邊界如何收縮）
- 重復(fù)時怎么取值
- 邊界情況取值
。。。
二分的思想很簡單，代碼量也很少，但是在文章開頭也提到過，手寫二分真不是一件容易的事情。
