二分查找算法是在有序数组中用到的较为频繁的一种算法，同样是一种很高效的算法，我们最长遇到的判断一个数字是不是在数组中，前提是数组是有序的，通常我们会数组进行遍历，跟每个元素进行比较，其时间为O(n).但二分查找算法则更优，因为其查找时间为O(lgn)，譬如数组{0，1， 2， 3， 4， 5， 6， 7， 8， 9}，查找元素3，用二分查找的算法执行的话，其顺序为：
1.第一步查找中间元素，即4，由于4>3，则3必然在4之前的数组元素中，那么就在{0，1， 2， 3}中查找，
2.寻找{0，1， 2， 3}的中位数，为1，1<3，则3应该在1右边的数组元素中，剩下2，3。
3.2和3的中间是2，2<3，最后3=3
二分查找算法就是不断将数组进行对半分割，每次拿中间元素和查找的数进行比较:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
-(
NSInteger
)binarySearch:(
NSMutableArray
*)array number:(
NSInteger
)number start:(
NSInteger
)start endIndex:(
NSInteger
)end{
while
(start<=end) {
NSInteger
middle=(start+end)/2;
if
([[array objectAtIndex:middle] integerValue]>number) {
end=middle-1;
}
else
if
([[array objectAtIndex:middle] integerValue]<number){
start=middle+1;
}
else
{
return
middle;
}
}
return
-1;
}
|
本文转自Fly_Elephant博客园博客，原文链接：http://www.cnblogs.com/xiaofeixiang/p/4537784.html，如需转载请自行联系原作者
