图片来自堆糖
如何确定一个数在一个有序数组中的位置？
假设有一个有序数组（注意：必须有序），我们要查找一个数在这个数组中的位置（index），如何查找？
不少人肯定首先会想到：哎，这个简单嘛，直接遍历不就OK咯？
- (NSInteger)indexOfTheNum:(NSInteger)num inTheArray:(NSArray *)array {
// 遍历
for (int i = 0; i < array.count; i++) {
// 比较
if ([array[i] integerValue] == num) {
// 找到这个数，返回index
return i;
}
}
// 没找到
return NULL;
}
这当然OK。
虽然很简单，但这其实也是一种算法，这种算法叫做简单查找。
当人品爆发时，在5个元素的数组中查找一个数只需找一次（遍历的第一个元素就是要找的），在10个元素的数组中查找某个数也只需找一次，100个元素、1万个元素、1亿个元素、n个元素，都只需找一次。当然，前提是人品爆发。
但是，当非酋附体时，要一直遍历到最后一个元素才找到要找的那个数，也就是说，n个元素的数组要找n次。
如何摆脱非酋附体时的困境？这个时候，可以考虑二分查找。
二分查找
简单查找是从头开始，依次一个一个的对比。
二分查找如它名字描述那样：从中间开始找。
比如说，有一个有序数组：
NSArray *array = @[@1, @3, @5, @7, @9, @10, @20];
要查找3在这个数组中的index。
首先，找到数组中间那个元素：7，3比7小，并且3比7后面的所有元素都小，所以现在只需要在7之前的元素中查找，也就是：
@[@1, @3, @5]
继续查找中间的那个元素，是3，OK，找到了。
用代码完整描述就是：
/**
二分查找
@param num 要查找的数
@param array 有序数组
@return 这个数在这个数组中的index
*/
- (NSInteger)binarySearchIndexOfNum:(NSInteger)num inArray:(NSArray *)array {
NSInteger minIndex = 0;
NSInteger maxIndex = array.count;
NSInteger midIndex = (minIndex + maxIndex) / 2;
// 中间的这个数
NSInteger midNum = [array[midIndex] integerValue];
while (num != midNum) {
if (num < midNum) {
maxIndex = midIndex - 1;
} else {
minIndex = midIndex + 1;
}
midIndex = (minIndex + maxIndex) / 2;
midNum = [array[midIndex] integerValue];
}
return midIndex;
}
二分查找，每查找一次都排除一半元素，直到最终剩下一个，这个就是我们要找的。
当非酋附体时（最糟糕的情况），使用二分查找，在4个元素的数组中查找需要两步，在8个元素的数组中查找需要3步，在1024个元素的数组中查找需要10步，在n个元素的数组中查找需要(log2 n)步，而简单查找需要n步，显然，当n越大时，简单查找跟二分查找效率的差距就越大。
时间复杂度
时间复杂度由大O表示法描述（大O，大写字母O，不是数字0）。
运用简单查找算法，在n个元素的数组中查找一个数，情况最遭时，需要n步，所以简单查找的时间复杂度是O(n)；
运用二分查找算法，在n个元素的数组中查找一个数，情况最遭时，需要(log2 n)步，所以二分查找的时间复杂度是O(log2 n)。
- 时间复杂度描述的就是非酋附体时的情况；
- 时间复杂度指的并非具体时间，而是操作数的增速。
网友评论