今天去参加面试的时候被提问到一个问题--请你解释一下二分查找。一时间忽然想不起来。于是乎回来复习了一下。
在百度百科里面是这样描述的：“二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。......”看到这里，我们应该大致明白了二分查找算法是怎么一回事了。但是如何表达才能在面试过程中让面试官刮目相看呢？
我们来分析一下，想让面试官刮目相看的话，可能会是什么原因？本人大致做这样的假设
1、回答得非常正确、专业
2、回答得非常生动、形象，通俗易懂
3、回答得非常全面
如果想让面试官在技术方面对你认可，必须表现得十分的专业，专业表现在表述知识的时候专业术语非常到位、其二表现在专业知识广泛，知道该知识点是什么、什么时候用，为什么这么用。如果能恰到好处的表现出这两点，那么面试官对你的看法应该就会大大提高，也有助于后面谈薪资的事情。
回到刚刚的问题上，假如刚才我们分析的几个方面就是令面试官刮目相看的点，那么我们应该怎么做呢？以本人为例子吧。假如要我背刚刚的那段话，说实话短期内背诵记住是完全没问题的，但是过几天又忘了。死记硬背是一件非常痛苦的事情。那么我们用联想记忆法试一下：该算法有两个名字（二分查找、折半查找）、优点三个（比较次数少、查找速度快、平均性能好）、缺点两个（待查找表为有序表、插入删除困难）。用数字表示就是232，图形表示就是=≠=（形容为 此二分非彼二分 ）
那么我们在面试的时候就可以这样表述：（面试的时候最好自带纸笔，原因不解释）用笔写出刚刚的=≠=的公式（原因是联想记忆更容易回忆起以前的内容），指着左边的等号跟面试官说“此二分非彼二分，二分查找不是简单的分两份，然后执行查找；它有两个名字，一个叫二分查找、另一个叫折半查找；就是在一个有序数组中，取数组中的中间值和要找的值进行比较，当要查找的值大于中间值，则在右边的区间继续取一个中间值和要比较的数进行比较。当找查找的值小于中间值时则反之，直至最后要查找的值和中间值相同，则说明找到该值。该算法有三个优点（指向中间的不等号），一是比较次数少、二是查找速度快、三是平均性能好。因为次数少了，速度自然快了，平均性能当然也就好了。但是呢，它也有两个缺点（指向右边的等号），其一是必须有序，没序的话，分成两份比较中间值的话没有意义，而排序本身是一件很耗时的运算；其二是增删困难，因为增删都要移动大量的结点。因此二分查找适用于那种一经建立就很少改动、而又经常需要查找的线性表（顺序存储结构）”到这里，如果能表达到这个程度已经是非常不错的了，但是如果能举个实际例子就更好了，因为面试官问你的初衷就是想知道你懂不懂，会不会用。而且本人写这篇的初衷也是想让阅读的人跟本人一样，从理解到能实际运用，这样对你、对我、对面试官都是一件好事不是吗？
（因为本人目前是做iOS的，因此举例用OC语法）在OC的NSArray中有三种以上的二分查找方法，分别是：CFArrayBSearchValues、indexOfObject:inSortedRange:options:usingComparator和自定义的二分查找。（本人在网上找到了以下几个例子供参考）：
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;
}
以上就是三个实例。那么在什么时候我们会用到呢？二分查找，查找，查找，当然是找东西的时候会用啦！当我们编写搜索算法时候会用到，因此记住，在项目遇到搜索、查找的时候，记得回忆起二分查找这个算法（当然也可以尝试用其他算法，比如冒泡、快排等等，具体的根据需求去分析即可）。
二分查找还有一些其他的注意事项，比如在Java中 二分查找的原始代码有几点需要注意的
intbinarySearch(intA[],intleft,intright,inttarget)
{intmid;
while(left<=right)
{mid=(left+right)/2;
if(A[mid])
returnmid;
elseright=mid-1;
}
return -1;
}
一是mid溢出、二是常数步的前进，具体就不展开叙述了，一般面试的时候都会考察边界条件迭代、循环终止条件设定以及中位数计算，如有兴趣可参考以下博客：二分查找的一些注意事项和在写二分查找的时候我在想些什么
以上就是本博客的全部内容，如有纰漏或建议请指教，十分感谢！
注：
OC三个实例例子来自于：一个关注移动互联网，iOS开发的个人博客。
