今天去參加面試的時候被提問到一個問題--請你解釋一下二分查找。一時間忽然想不起來。于是乎回來復(fù)習(xí)了一下。
在百度百科里面是這樣描述的：“二分查找又稱折半查找，優(yōu)點是比較次數(shù)少，查找速度快，平均性能好；其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經(jīng)常變動而查找頻繁的有序列表。......”看到這里，我們應(yīng)該大致明白了二分查找算法是怎么一回事了。但是如何表達才能在面試過程中讓面試官刮目相看呢？
我們來分析一下，想讓面試官刮目相看的話，可能會是什么原因？本人大致做這樣的假設(shè)
1、回答得非常正確、專業(yè)
2、回答得非常生動、形象，通俗易懂
3、回答得非常全面
如果想讓面試官在技術(shù)方面對你認可，必須表現(xiàn)得十分的專業(yè)，專業(yè)表現(xiàn)在表述知識的時候?qū)I(yè)術(shù)語非常到位、其二表現(xiàn)在專業(yè)知識廣泛，知道該知識點是什么、什么時候用，為什么這么用。如果能恰到好處的表現(xiàn)出這兩點，那么面試官對你的看法應(yīng)該就會大大提高，也有助于后面談薪資的事情。
回到剛剛的問題上，假如剛才我們分析的幾個方面就是令面試官刮目相看的點，那么我們應(yīng)該怎么做呢？以本人為例子吧。假如要我背剛剛的那段話，說實話短期內(nèi)背誦記住是完全沒問題的，但是過幾天又忘了。死記硬背是一件非常痛苦的事情。那么我們用聯(lián)想記憶法試一下：該算法有兩個名字（二分查找、折半查找）、優(yōu)點三個（比較次數(shù)少、查找速度快、平均性能好）、缺點兩個（待查找表為有序表、插入刪除困難）。用數(shù)字表示就是232，圖形表示就是=≠=（形容為 此二分非彼二分 ）
那么我們在面試的時候就可以這樣表述：（面試的時候最好自帶紙筆，原因不解釋）用筆寫出剛剛的=≠=的公式（原因是聯(lián)想記憶更容易回憶起以前的內(nèi)容），指著左邊的等號跟面試官說“此二分非彼二分，二分查找不是簡單的分兩份，然后執(zhí)行查找；它有兩個名字，一個叫二分查找、另一個叫折半查找；就是在一個有序數(shù)組中，取數(shù)組中的中間值和要找的值進行比較，當(dāng)要查找的值大于中間值，則在右邊的區(qū)間繼續(xù)取一個中間值和要比較的數(shù)進行比較。當(dāng)找查找的值小于中間值時則反之，直至最后要查找的值和中間值相同，則說明找到該值。該算法有三個優(yōu)點（指向中間的不等號），一是比較次數(shù)少、二是查找速度快、三是平均性能好。因為次數(shù)少了，速度自然快了，平均性能當(dāng)然也就好了。但是呢，它也有兩個缺點（指向右邊的等號），其一是必須有序，沒序的話，分成兩份比較中間值的話沒有意義，而排序本身是一件很耗時的運算；其二是增刪困難，因為增刪都要移動大量的結(jié)點。因此二分查找適用于那種一經(jīng)建立就很少改動、而又經(jīng)常需要查找的線性表（順序存儲結(jié)構(gòu)）”到這里，如果能表達到這個程度已經(jīng)是非常不錯的了，但是如果能舉個實際例子就更好了，因為面試官問你的初衷就是想知道你懂不懂，會不會用。而且本人寫這篇的初衷也是想讓閱讀的人跟本人一樣，從理解到能實際運用，這樣對你、對我、對面試官都是一件好事不是嗎？
（因為本人目前是做iOS的，因此舉例用OC語法）在OC的NSArray中有三種以上的二分查找方法，分別是：CFArrayBSearchValues、indexOfObject:inSortedRange:options:usingComparator和自定義的二分查找。（本人在網(wǎng)上找到了以下幾個例子供參考）：
CFArray的二分查找方法
NSMutableArray *sortedArray = [NSMutableArray arrayWithObjects: @"Alice", @"Beth", @"Carol",@"Ellen",nil];
//Where is "Beth"?
unsigned index = (unsigned)CFArrayBSearchValues((CFArrayRef)sortedArray,
CFRangeMake(0, CFArrayGetCount((CFArrayRef)sortedArray)),
(CFStringRef)@"Beth",
(CFComparatorFunction)CFStringCompare,
NULL);
if (index < [sortedArray count] && [@"Beth" isEqualToString:sortedArray[index]])
{
NSLog(@"Beth was found at index %u", index);
} else {
NSLog(@"Beth was not found (index is beyond the bounds of sortedArray)");
}
//Where should we insert "Debra"?
unsigned insertIndex = (unsigned)CFArrayBSearchValues((CFArrayRef)sortedArray,
CFRangeMake(0, CFArrayGetCount((CFArrayRef)sortedArray)),
(CFStringRef)@"Debra",
(CFComparatorFunction)CFStringCompare,
NULL);
[sortedArray insertObject:@"Debra" atIndex:insertIndex];
NSLog(@"%@",sortedArray);
NSArray的二分查找方法
NSArray *sortedArray = ... // must be sorted
id searchObject = ...
NSRange searchRange = NSMakeRange(0, [sortedArray count]);
NSUInteger findIndex = [sortedArray indexOfObject:searchObject
inSortedRange:searchRange
options:NSBinarySearchingFirstEqual
usingComparator:^(id obj1, id obj2)
{
return [obj1 compare:obj2];
}];
自己編寫二分查找算法
int main(int argc, const char * argv[])
{
@autoreleasepool {
// Conceptual tutorial
NSArray *numberArray = @[@1, @3, @27, @36, @42, @70, @82];
NSNumber *searchNum = @70;
NSUInteger mid;
NSUInteger min = 0;
NSUInteger max = [numberArray count] - 1;
BOOL found = NO;
while (min <= max) {
mid = (min + max)/2;
if ([searchNum intValue] == [numberArray[mid] intValue]) {
NSLog(@"We found the number! It is at index %lu", mid);
found = YES;
break;
} else if ([searchNum intValue] < [numberArray[mid] intValue]) {
max = mid - 1;
} else if ([searchNum intValue] > [numberArray[mid] intValue]) {
min = mid + 1;
}
}
if (!found) {NSLog(@"The number was not found.");
}
}
return 0;
}
以上就是三個實例。那么在什么時候我們會用到呢？二分查找，查找，查找，當(dāng)然是找東西的時候會用啦！當(dāng)我們編寫搜索算法時候會用到，因此記住，在項目遇到搜索、查找的時候，記得回憶起二分查找這個算法（當(dāng)然也可以嘗試用其他算法，比如冒泡、快排等等，具體的根據(jù)需求去分析即可）。
二分查找還有一些其他的注意事項，比如在Java中 二分查找的原始代碼有幾點需要注意的
intbinarySearch(intA[],intleft,intright,inttarget)
{intmid;
while(left<=right)
{mid=(left+right)/2;
if(A[mid])
returnmid;
elseright=mid-1;
}
return -1;
}
一是mid溢出、二是常數(shù)步的前進，具體就不展開敘述了，一般面試的時候都會考察邊界條件迭代、循環(huán)終止條件設(shè)定以及中位數(shù)計算，如有興趣可參考以下博客：二分查找的一些注意事項和在寫二分查找的時候我在想些什么
以上就是本博客的全部內(nèi)容，如有紕漏或建議請指教，十分感謝！
注：
OC三個實例例子來自于：一個關(guān)注移動互聯(lián)網(wǎng)，iOS開發(fā)的個人博客。
