算法：从二分查找到时间复杂度

图片来自堆糖

如何确定一个数在一个有序数组中的位置？

假设有一个有序数组（注意：必须有序），我们要查找一个数在这个数组中的位置（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)。

• 时间复杂度描述的就是非酋附体时的情况；
• 时间复杂度指的并非具体时间，而是操作数的增速。