一維數(shù)組
首先開(kāi)始最基本的Binary Search, 數(shù)組是有序的辙纬，但是有重復(fù)數(shù)。
例題： Search for a Range
復(fù)雜度：時(shí)間O(log n), 空間O(1).
分析： 首先需要復(fù)雜度在O(log n)左右，顯然暗示了Binary Search是首選，然后注意這道題是需要找到一個(gè)range，并不是找到target的位置就可以了抛腕。因此在找到位置后，分別向左向右拓展到兩邊媒殉，返回這兩個(gè)數(shù)就可以了担敌。
class Solution{
public:
vector<int> searchRange(int A[], int n, int target) {
vector<int> result(2,-1);
int index = search(A, n, target);
if(index == -1) return result;
int l = index, r = index;
while(l -1 >= 0 && A[l] == A[l-1]) --l;
while(r +1 <= n-1 && A[r] == A[r+1]) ++r;
result[0] = l;
result[1] = r;
return result;
}
int search(int A[], int n , int target){
if(A == nullptr || n == 0) return -1;
int left = 0, right = n -1;
while(left <= right){
int mid = left + (right - left) /2;
if(target > A[mid])
left = mid + 1;
else if(target < A[mid])
right = mid - 1;
else if(target == A[mid])
return mid;
}
return -1;
}
};
注意這里做binary search時(shí)候，對(duì)于A[mid]分為了三種不同情況討論廷蓉，相等全封，小于和大于，并且while循環(huán)的終止條件是left <= right桃犬，也就是說(shuō)最后left > right時(shí)候表明目標(biāo)數(shù)肯定不存在了刹悴。在對(duì)于不同的問(wèn)題，這些邊界條件會(huì)相應(yīng)的改變攒暇。另外這樣搜索如果最后目標(biāo)數(shù)存在土匀，最后結(jié)果一定是以A[mid]的形式。
例題： Search Insert Position
復(fù)雜度：時(shí)間O(log n), 空間O(1).
分析：這道題的關(guān)鍵是如果目標(biāo)數(shù)不存在形用，必須返回目標(biāo)數(shù)可以插入的位置就轧，這樣經(jīng)典的binary search返回A[mid]的方法（如上題）沒(méi)法直接實(shí)現(xiàn)因此必須對(duì)循環(huán)的條件以及邊界進(jìn)行調(diào)整。首先當(dāng)循環(huán)結(jié)束時(shí)候尾序，為了能返回一個(gè)目標(biāo)數(shù)可以插入的地址钓丰，我們必須讓left == right也就是說(shuō)循環(huán)條件相應(yīng)調(diào)整為left < right. 如果需要設(shè)置循環(huán)里面的邊界條件和left, right的初始條件，我們必須看一下最后一次循環(huán)時(shí)候的情況：最后一次循環(huán)時(shí)每币， left + 1 = right只剩下兩個(gè)元素需要考慮（這里忽略數(shù)組只有一個(gè)元素的情形，因?yàn)橐粋€(gè)元素時(shí)琢歇，程序根本不會(huì)進(jìn)入循環(huán)）兰怠，此時(shí)mid = left梦鉴，如果target > A[mid], left = mid + 1 = right與之前情況類(lèi)似，那么當(dāng)target < A[mid]時(shí)候也就是說(shuō)target并不存在揭保，此時(shí)應(yīng)該輸出target元素需要插入的位置也就是left, 因此right = mid = left肥橙，當(dāng)target = A[mid]情形與小于相同，right = mid = left.還有一種情況秸侣，當(dāng)target大于數(shù)組里面所有數(shù)的時(shí)候存筏，插入位置應(yīng)該在所有數(shù)組之后，因此right的初始值必須是n味榛，因?yàn)楹苋菀装l(fā)現(xiàn)前面的邊界條件設(shè)置導(dǎo)致最后輸出的left都會(huì)在兩個(gè)初始值left和right之間椭坚。
class Solution {
public:
int searchInsert(int A[], int n, int target) {
if(A == nullptr || n == 0) return -1;
int left = 0, right = n ;
while(left < right){
int mid = left + (right - left) /2 ;
if(target > A[mid])
left = mid + 1;
else
right = mid;
}
return left;
}
};
接下來(lái)，問(wèn)題難度提高了搏色，數(shù)組仍然有序并且無(wú)重復(fù)數(shù)善茎，但是在某一點(diǎn)pivot截?cái)嗖⑶乙苿?dòng)了幾位。
例題： Search in Rotated Sorted Array
復(fù)雜度： 時(shí)間O(log n), 空間O(1).
分析：因?yàn)槭孪炔恢罃?shù)組會(huì)再哪里截?cái)嘁虼嗽趙hile循環(huán)的邊界條件需要調(diào)整來(lái)滿(mǎn)足需求频轿。因?yàn)榇嬖跀?shù)組中并不包含目標(biāo)數(shù)的情況垂涯，因此希望所有循環(huán)結(jié)束時(shí)候仍然找不到目標(biāo)數(shù)此時(shí)返回-1，另一方面也就是說(shuō)在循環(huán)內(nèi)部如果發(fā)現(xiàn)目標(biāo)數(shù)A[mid] == target返回航邢，當(dāng)first == last時(shí)候循環(huán)結(jié)束耕赘， 判斷條件與上一道題一樣。下面看A[mid] != target的情形膳殷，因?yàn)閜ivot的存在鞠苟，必須找到pivot在左邊還是右邊，辦法就是比較A[first]和A[mid]秽之，如果A[first] < A[mid]說(shuō)明pivot不在左邊這段当娱，因?yàn)閜ivot會(huì)破壞所在一段的連續(xù)遞增性（遞減性）, 因此這里在左邊用一般的binary search可以解決。如果A[first] > A[mid],pivot肯定會(huì)在左邊考榨，那么我們可以對(duì)右邊進(jìn)行binary search因?yàn)橛疫吺沁B續(xù)遞增（遞減）的跨细。下面再考慮邊界條件還有初始條件，注意這里我們還是把初始條件設(shè)置為n即最后一位之后一位河质，那么在邊界條件上需要變化冀惭，如果target屬于[A[first], A[mid])之間，last變?yōu)閙id掀鹅，注意這里保持last是搜索范圍最后一個(gè)數(shù)字的下一位散休。 同理在A[first] > A[mid]的情況下我們比較的是target <= A[last -1 ]由于last的初始值設(shè)置。 注意在討論target和左右兩個(gè)邊界條件時(shí)候使用大于等于或者小于等于乐尊，注意等號(hào)是必須的戚丸。
class Solution {
public:
int search(int A[], int n, int target) {
if(A == nullptr || n == 0) return -1;
int first = 0, last = n;
while (first < last) {
int mid = first + (last - first) / 2;
if (A[mid] == target)
return mid;
if (A[first] < A[mid]) {
if (A[first] <= target && target < A[mid])
last = mid;
else
first = mid + 1;
} else {
if (A[mid] < target && target <= A[last-1])
first = mid + 1;
else
last = mid;
}
}
return -1;
}
};
下面繼續(xù)提高難度，如果上面的那道題數(shù)組是可重復(fù)的呢扔嵌？
例題：Rotated Sorted Array II
復(fù)雜度：時(shí)間O(n),空間O(1).
分析：如果出現(xiàn)重復(fù)數(shù)最大的問(wèn)題就是當(dāng)A[left] == A[mid],此時(shí)沒(méi)有辦法判斷pivot到底在哪里限府，比較簡(jiǎn)單的快速解決方案就是把left右移一位繼續(xù)尋找夺颤。
class Solution {
public:
bool search(int A[], int n, int target) {
if(A == nullptr|| n == 0) return false;
int left = 0, right = n;
while(left < right){
int mid = left + (right - left)/2;
if(A[mid] == target)
return true;
if(A[left] < A[mid]){
if(target < A[mid] && target >= A[left]){
right = mid;
}else{
left = mid + 1;
}
}else if(A[left] > A[mid]){
if(target <= A[right -1 ] && target > A[mid]){
left = mid + 1;
}else{
right = mid;
}
}else{
left++;
}
}
return false;
}
};
下面我們看一看數(shù)組查找的變形
例題：Find Minimum in Rotated Sorted Array
復(fù)雜度： 時(shí)間O(log n)，空間O(1).
分析：首先這道題和上兩道題非常相似胁勺，唯一的區(qū)別就是目標(biāo)不同：尋找最小值即pivot世澜。首先假設(shè)變形前數(shù)組是從左至右遞增，變形之后我們可以很容易發(fā)現(xiàn)最左邊的元素num[left]永遠(yuǎn)大于最右邊的元素mum[right]即num[left] > num[right]因?yàn)閿?shù)組里沒(méi)有重復(fù)元素署穗。與之前不同寥裂，我們這里要找到pivot所在的區(qū)域而不是要避開(kāi)，因此在循環(huán)內(nèi)我們要比較的事num[mid]和num[right]之間的關(guān)系這道題不能比較num[start]和num[mid]因?yàn)闆](méi)法排除特例當(dāng)start == mid案疲，如果num[mid] > num[right]即數(shù)組的遞增性在右邊是被破壞的封恰，因此pivot肯定是在右邊［mid+1, right]，反之則是［left, mid].最后我們考慮終結(jié)條件络拌，我們知道pivot有一個(gè)性質(zhì)就是唯一存在i so that num[i -1] > num[i],這里num[i]就是pivot.我們看一下最后一次循環(huán)的情形俭驮，此時(shí)left + 1 = right 并且mid = left， 這里如果如果num[mid] > num[right],那么pivot就是left = right = mid + 1, 反之right = left = mid春贸，因此跳出循環(huán)后left = right就是pivot所在的位置混萝。
class Solution {
public:
int findMin(vector<int> &num) {
if(num.empty()) return 0;
int left = 0;
int right = n - 1;
while(left < right ){
int mid = left + (right - left)/2;
if(num[mid] > num[right]){
left = mid + 1;
}else {
right = mid ;
}
}
return num[left];
}
};
繼續(xù)增加難度，如果允許重復(fù)數(shù)的存在呢萍恕？
例題：Find Minimum in Rotated Sorted Array II
復(fù)雜度： 時(shí)間O(n), 空間O(1).
分析：如果出現(xiàn)重復(fù)數(shù)逸嘀，唯一一種情況沒(méi)辦法處理就是A[mid] == A[left] == A[right],這次我們不采用上次的簡(jiǎn)單fix（把左邊邊界往右邊移一位），而是寫(xiě)成recursive的形式在左右兩邊分別尋找最小值允粤，這樣復(fù)雜度會(huì)提高到O(n)了崭倘。
class Solution {
public:
int findMin(vector<int> &num) {
return findmin(num, 0, num.size() -1);
}
int findmin(vector<int> &num, int left, int right){
if(num.size() == 0) return -1;
while(left < right){
int mid = left + (right - left)/2;
if(num[mid] > num[right]){
left = mid + 1;
}else if(num[mid] < num[right]){
right = mid;
}else{
return min(findmin(num, left, mid), findmin(num, mid+1, right));
}
}
return num[left];
}
};
在我們結(jié)束探討一維數(shù)組之前，再看一個(gè)經(jīng)典的利用二分法查找的一維數(shù)組問(wèn)題
例題： Median of Two Sorted Array
分析： 首先得弄明白median的定義类垫，如果數(shù)組包含偶數(shù)個(gè)元素司光，median取中間兩個(gè)數(shù)的平均值；如果數(shù)組包含個(gè)奇數(shù)個(gè)元素悉患，那么median就是中間的那個(gè)數(shù)残家。下面繼續(xù)看這道題，需要尋找的是兩個(gè)排序的數(shù)組median售躁，自然想到使用二分法來(lái)解坞淮。利用recursive的方法，每次比較數(shù)組A的中位數(shù)A[n/2]和數(shù)組B的中位數(shù)B[m/2]陪捷，比較同時(shí)在考慮比較另外兩個(gè)值m/2 + n/2 + 1和k(其中k是兩個(gè)數(shù)組合并后的第k個(gè)元素),這樣可以確定刪除哪一部分繼續(xù)搜索回窘，原則是丟棄最大中位數(shù)的右區(qū)間或者最小中位數(shù)的左區(qū)間。最后就是邊界條件的確定市袖，假設(shè)其中一個(gè)數(shù)組為空了啡直，那么返回的就是另一個(gè)數(shù)組的最后一個(gè)數(shù)。或者如果k = 1付枫， 那么返回兩個(gè)數(shù)組中第一個(gè)元素的較小值烹玉。
class Solution {
public:
double findMedianSortedArrays(int A[], int m, int B[], int n) {
if((m+n) %2 == 1){
return findMedian(A, m, B, n, (m+n)/ 2 + 1);
}else{
return (findMedian(A, m, B, n, (m+n)/2) + findMedian(A, m, B, n, (m+n)/2 + 1))/2.0;
}
}
private:
double findMedian(int A[], int m, int B[], int n, int k){
assert(A&&B);
if(m <= 0) return B[k-1];
if(n <= 0) return A[k-1];
if(k == 1) return min(A[0], B[0]);
if(B[n/2] >= A[m/2]){
if((m/2 + n/2 + 1) >= k)
return findMedian(A, m, B, n/2, k);
else
return findMedian(A + m/2 + 1, m - (m/2 + 1), B, n, k - m/2 -1);
}else{
if((m/2 + n/2 + 1) >= k)
return findMedian(A, m/2, B, n, k);
else
return findMedian(A, m, B + n/2 + 1, n - (n/2 + 1), k - n/2 - 1);
}
}
};
這道題還有更簡(jiǎn)潔的方法驰怎，即確保A數(shù)組的個(gè)數(shù)永遠(yuǎn)不大于B數(shù)組的個(gè)數(shù)阐滩，如果不是就交換這兩個(gè)數(shù)組。
class Solution {
public:
double findMedianSortedArrays(int A[], int m, int B[], int n) {
int total = m + n;
if( total & 0x1 ){
return findMedian(A, m, B, n, total/2 + 1);
}else{
return (findMedian(A, m, B, n, total/2) + findMedian(A, m, B, n, total/2 + 1))/2.0;
}
}
private:
int findMedian(int A[], int m, int B[], int n, int k){
if(m > n) return findMedian(B, n, A, m, k);
if(m == 0) return B[k-1];
if(k == 1) return min(A[0], B[0]);
int ia = min(k/2, m), ib = k - ia;
if(A[ia-1] < B[ib-1])
return findMedian(A + ia, m -ia, B, n, k -ia);
else if(A[ia - 1] > B[ib - 1])
return findMedian(A, m, B +ib, n -ib, k -ib);
else
return A[ia - 1];
}
};
二維數(shù)組
例題： Search a 2D matrix
復(fù)雜度： 時(shí)間O(log (m*n)), 空間O(1).
分析：首先這道題中二維數(shù)組有兩個(gè)特點(diǎn)：
- 每一行數(shù)是遞增的
- 每一行第一個(gè)數(shù)都小于上一行的最后一個(gè)數(shù)
因此很自然的想到把二維數(shù)組壓平為一位數(shù)組县忌，然后使用binary search解決掂榔。
class Solution {
public:
bool searchMatrix(vector<vector<int> > &matrix, int target) {
if(matrix.empty() || matrix.front().size()) return false;
int m = matrix.size();
int n = matrix.front().size();
int left = 0;
int right = m*n;
while(left < right){
int mid = left + (right - left) /2;
int middle = matrix[mid / n][mid % n];
if(target == middle){
return true;
}else if(target > middle){
left = mid + 1;
}else{
right = mid;
}
}
return false;
}
};
