二分查找算法是在有序数组中用到的较为频繁的一种算法，同样是一种很高效的算法，我们最长遇到的判断一个数字是不是在数组中，前提是数组是有序的，通常我们会数组进行遍历，跟每个元素进行比较，其时间为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;
} |