今天去參加面試的時(shí)候被提問到一個(gè)問題--請(qǐng)你解釋一下二分查找蕉扮。一時(shí)間忽然想不起來。于是乎回來復(fù)習(xí)了一下背亥。
在百度百科里面是這樣描述的：“二分查找又稱折半查找我纪，優(yōu)點(diǎn)是比較次數(shù)少，查找速度快潜支，平均性能好甸赃；其缺點(diǎn)是要求待查表為有序表，且插入刪除困難毁腿。因此辑奈，折半查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表苛茂。......”看到這里，我們應(yīng)該大致明白了二分查找算法是怎么一回事了鸠窗。但是如何表達(dá)才能在面試過程中讓面試官刮目相看呢妓羊？
我們來分析一下，想讓面試官刮目相看的話稍计，可能會(huì)是什么原因躁绸？本人大致做這樣的假設(shè)
1、回答得非常正確臣嚣、專業(yè)
2净刮、回答得非常生動(dòng)、形象硅则，通俗易懂
3淹父、回答得非常全面
如果想讓面試官在技術(shù)方面對(duì)你認(rèn)可，必須表現(xiàn)得十分的專業(yè)怎虫，專業(yè)表現(xiàn)在表述知識(shí)的時(shí)候?qū)I(yè)術(shù)語(yǔ)非常到位暑认、其二表現(xiàn)在專業(yè)知識(shí)廣泛，知道該知識(shí)點(diǎn)是什么大审、什么時(shí)候用蘸际，為什么這么用。如果能恰到好處的表現(xiàn)出這兩點(diǎn)徒扶，那么面試官對(duì)你的看法應(yīng)該就會(huì)大大提高粮彤，也有助于后面談薪資的事情。
回到剛剛的問題上姜骡，假如剛才我們分析的幾個(gè)方面就是令面試官刮目相看的點(diǎn)导坟，那么我們應(yīng)該怎么做呢？以本人為例子吧溶浴。假如要我背剛剛的那段話乍迄，說實(shí)話短期內(nèi)背誦記住是完全沒問題的，但是過幾天又忘了士败。死記硬背是一件非常痛苦的事情。那么我們用聯(lián)想記憶法試一下：該算法有兩個(gè)名字（二分查找褥伴、折半查找）谅将、優(yōu)點(diǎn)三個(gè)（比較次數(shù)少、查找速度快重慢、平均性能好）饥臂、缺點(diǎn)兩個(gè)（待查找表為有序表、插入刪除困難）似踱。用數(shù)字表示就是232隅熙，圖形表示就是=≠=（形容為 此二分非彼二分 ）
那么我們?cè)诿嬖嚨臅r(shí)候就可以這樣表述：（面試的時(shí)候最好自帶紙筆稽煤，原因不解釋）用筆寫出剛剛的=≠=的公式（原因是聯(lián)想記憶更容易回憶起以前的內(nèi)容），指著左邊的等號(hào)跟面試官說“此二分非彼二分囚戚，二分查找不是簡(jiǎn)單的分兩份酵熙，然后執(zhí)行查找；它有兩個(gè)名字驰坊，一個(gè)叫二分查找匾二、另一個(gè)叫折半查找；就是在一個(gè)有序數(shù)組中拳芙，取數(shù)組中的中間值和要找的值進(jìn)行比較察藐，當(dāng)要查找的值大于中間值，則在右邊的區(qū)間繼續(xù)取一個(gè)中間值和要比較的數(shù)進(jìn)行比較舟扎。當(dāng)找查找的值小于中間值時(shí)則反之分飞，直至最后要查找的值和中間值相同，則說明找到該值睹限。該算法有三個(gè)優(yōu)點(diǎn)（指向中間的不等號(hào)）譬猫，一是比較次數(shù)少、二是查找速度快邦泄、三是平均性能好删窒。因?yàn)榇螖?shù)少了，速度自然快了顺囊，平均性能當(dāng)然也就好了肌索。但是呢，它也有兩個(gè)缺點(diǎn)（指向右邊的等號(hào)）特碳，其一是必須有序诚亚，沒序的話，分成兩份比較中間值的話沒有意義午乓，而排序本身是一件很耗時(shí)的運(yùn)算站宗；其二是增刪困難，因?yàn)樵鰟h都要移動(dòng)大量的結(jié)點(diǎn)益愈。因此二分查找適用于那種一經(jīng)建立就很少改動(dòng)梢灭、而又經(jīng)常需要查找的線性表（順序存儲(chǔ)結(jié)構(gòu)）”到這里，如果能表達(dá)到這個(gè)程度已經(jīng)是非常不錯(cuò)的了蒸其，但是如果能舉個(gè)實(shí)際例子就更好了敏释，因?yàn)槊嬖嚬賳柲愕某踔跃褪窍胫滥愣欢瑫?huì)不會(huì)用摸袁。而且本人寫這篇的初衷也是想讓閱讀的人跟本人一樣钥顽，從理解到能實(shí)際運(yùn)用，這樣對(duì)你靠汁、對(duì)我蜂大、對(duì)面試官都是一件好事不是嗎闽铐？
（因?yàn)楸救四壳笆亲鰅OS的，因此舉例用OC語(yǔ)法）在OC的NSArray中有三種以上的二分查找方法奶浦，分別是：CFArrayBSearchValues兄墅、indexOfObject:inSortedRange:options:usingComparator和自定義的二分查找。（本人在網(wǎng)上找到了以下幾個(gè)例子供參考）：
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;
}
以上就是三個(gè)實(shí)例财喳。那么在什么時(shí)候我們會(huì)用到呢察迟？二分查找，查找耳高，查找扎瓶，當(dāng)然是找東西的時(shí)候會(huì)用啦！當(dāng)我們編寫搜索算法時(shí)候會(huì)用到泌枪，因此記住概荷，在項(xiàng)目遇到搜索、查找的時(shí)候碌燕，記得回憶起二分查找這個(gè)算法（當(dāng)然也可以嘗試用其他算法误证，比如冒泡、快排等等修壕，具體的根據(jù)需求去分析即可）愈捅。
二分查找還有一些其他的注意事項(xiàng)，比如在Java中 二分查找的原始代碼有幾點(diǎn)需要注意的
intbinarySearch(intA[],intleft,intright,inttarget)
{intmid;
while(left<=right)
{mid=(left+right)/2;
if(A[mid])
returnmid;
elseright=mid-1;
}
return -1;
}
一是mid溢出慈鸠、二是常數(shù)步的前進(jìn)痘煤，具體就不展開敘述了刷允，一般面試的時(shí)候都會(huì)考察邊界條件迭代豁生、循環(huán)終止條件設(shè)定以及中位數(shù)計(jì)算组哩，如有興趣可參考以下博客：二分查找的一些注意事項(xiàng)和在寫二分查找的時(shí)候我在想些什么
以上就是本博客的全部?jī)?nèi)容，如有紕漏或建議請(qǐng)指教督笆，十分感謝芦昔！
注：
OC三個(gè)實(shí)例例子來自于：一個(gè)關(guān)注移動(dòng)互聯(lián)網(wǎng)，iOS開發(fā)的個(gè)人博客娃肿。
