前言

從前端轉(zhuǎn)型搞iOS近三年了，最近技術(shù)進(jìn)階很艱難，反思和整理之后，覺(jué)得是『內(nèi)功』修煉不夠，所以現(xiàn)在的我要忘掉所有招式，回歸基本功的修煉，希望有緣看到本篇文章的大神，可以不吝指導(dǎo)，謝謝。

都說(shuō)天下武功出少林，同樣，所有的編程開(kāi)發(fā)語(yǔ)言中萬(wàn)變不離其宗的應(yīng)該就是算法和理論了，算法可算是程序的靈魂。

要想有個(gè)強(qiáng)大的靈魂，我打算重新修煉基本功——算法。

先從『二分法』開(kāi)始：

算法原理

假設(shè)需要查找的值為x，檢索的數(shù)組為array。

1. 確定查找范圍 from = 0，end = array.count - 1，計(jì)算中項(xiàng) middle= (from + end) / 2。
2. 若 array[middle] = x 或 from >= end, 則結(jié)束查找；否則，向下繼續(xù)。
3. 若 array[middle] < x, 說(shuō)明待查找的元素值只可能在比中項(xiàng)元素大的范圍內(nèi)，則把 middle + 1 的值賦給from，并重新計(jì)算middle，轉(zhuǎn)去執(zhí)行步驟2；
4. 若 array[middle] > x，說(shuō)明待查找的元素值只可能在比中項(xiàng)元素小的范圍內(nèi)，則把 middle - 1 的值賦給end，并重新計(jì)算middle，轉(zhuǎn)去執(zhí)行步驟2。

適用范圍

二分法是一種非常高效的數(shù)據(jù)查找算法，通常適用二分法的都有以下特征：

1. 數(shù)據(jù)量大；
2. 數(shù)據(jù)為有序的；
3. 需要在大量數(shù)據(jù)中定位某個(gè)值或找出某個(gè)值的索引值；

運(yùn)用

場(chǎng)景：在一個(gè)升序的數(shù)組 [21, 23, 25, 27, ... , 53 ]中獲取 31 的索引值，如31不在數(shù)組中，則返回-1；

- (void)viewDidLoad {
    [super viewDidLoad];

    NSArray *array = @[@11, @23, @29, @31, @33, @35, @37, @47, @71, @99];

    NSInteger key = 23;

    NSLog(@"key 在數(shù)組 array 中的索引是：%ld", [self getIndexOfKey:key atArray:array]);
}

- (NSInteger)getIndexOfKey: (NSInteger)key atArray: (NSArray *)array {

    NSInteger min = 0, mid = 0, max = array.count-1;

    while (min <= max) {
    
        mid = (min + max) / 2;
    
        if (key == [array[mid] integerValue]) {
        
            return mid;
        }
    
        else if (key > [array[mid] integerValue]) {
        
            min = mid + 1;
        }
    
        else if (key < [array[mid] integerValue]) {
        
            max = mid - 1;
        }
    }

    return -1;
}

https://baike.baidu.com/item/二分法查找/9751511?fr=aladdin
http://www.baike.com/wiki/二分法