IOS查找算法之二分查找

二分查找（Binary Search）算法勒叠，也叫折半查找算法欧漱。二分查找的思想非常簡單职抡，很多非計算機專業(yè)的同學很容易就能理解，但是看似越簡單的東西往往越難掌握好误甚，想要靈活應用就更加困難缚甩。

無處不在的二分思想

舉個例子：我們假設只有 10 個訂單谱净，訂單金額分別是：8，11擅威，19壕探，23，27郊丛，33李请，45，55厉熟，67导盅，98。還是利用二分思想揍瑟，每次都與區(qū)間的中間數據比對大小白翻，縮小查找區(qū)間的范圍。為了更加直觀绢片，我畫了一張查找過程的圖滤馍。其中，low 和 high 表示待查找區(qū)間的下標杉畜，mid 表示待查找區(qū)間的中間元素下標纪蜒。

image.png

總結一下：二分查找針對的是一個有序的數據集合，查找思想有點類似分治思想此叠。每次都通過跟區(qū)間的中間元素對比纯续，將待查找的區(qū)間縮小為之前的一半，直到找到要查找的元素灭袁，或者區(qū)間被縮小為 0猬错。

O(logn) 驚人的查找速度

二分查找是一種非常高效的查找算法，高效到什么程度呢茸歧？我們來分析一下它的時間復雜度倦炒。

我們假設數據大小是 n，每次查找后數據都會縮小為原來的一半软瞎，也就是會除以 2逢唤。最壞情況下，直到查找區(qū)間被縮小為空涤浇，才停止鳖藕。

image.png

可以看出來，這是一個等比數列只锭。其中 n/2k=1 時著恩，k 的值就是總共縮小的次數。而每一次縮小操作只涉及兩個數據的大小比較，所以喉誊，經過了 k 次區(qū)間縮小操作邀摆，時間復雜度就是 O(k)。通過 n/2k=1伍茄，我們可以求得 k=log2n栋盹，所以時間復雜度就是 O(logn)。

這是一種極其高效的時間復雜度敷矫，有的時候甚至比時間復雜度是常量級 O(1) 的算法還要高效贞盯。為什么這么說呢？

因為logn 是一個非郴龋“恐怖”的數量級，即便n非常非常大闷愤，對應的logn也很小整葡。比如n等于2的32次方，這個數很大了吧?大約是42億讥脐。也就是說遭居，如果我們在42億個數據中用二分查找一個數據，最多需要比較32次旬渠。

我們前面講過俱萍，用大0標記法表示時間復雜度的時候，會省略掉常數告丢、系數和低階枪蘑。對于常量級時間復雜度的算法來說，0(1) 有可能表示的是一個非常大的常量值岖免，比如O(1000)岳颇、O(10000)。所以颅湘，常量級時間復雜度的算法有時候可能還沒有O(logn) 的算法執(zhí)行效率高话侧。

二分查找的遞歸與非遞歸實現

實際上，簡單的二分查找并不難寫闯参，注意我這里的“簡單”二字瞻鹏。下一節(jié)，我們會講到二分查找的變體問題鹿寨，那才是真正燒腦的新博。今天，我們來看如何來寫最簡單的二分查找释移。

最簡單的情況就是有序數組中不存在重復元素叭披，我們在其中用二分查找值等于給定值的數據。我用IOS代碼實現了一個最簡單的二分查找算法。

- (NSInteger)gly_bsearchWithLoop:(NSString *)propertyName value:(double)value
{
    NSInteger low = 0;
    NSInteger high = self.count - 1;
    
    while (low <= high)
    {
        //為什么不寫(low + high) / 2涩蜘，是因為如果 low 和 high 比較大的話嚼贡，兩者之和就有可能會溢出。
        NSInteger mid = low + ((high - low) >> 1);
        double middleNumber = [[self[mid] valueForKey:propertyName] doubleValue];
        if ([@(middleNumber) compare:@(value)] == NSOrderedSame)
        {
            return mid;
        }
        else if ([@(middleNumber) compare:@(value)] == NSOrderedAscending)
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    
    return -1;
}

這個代碼我稍微解釋一下同诫，low粤策、high、mid 都是指數組下標误窖，其中 low 和 high 表示當前查找的區(qū)間范圍叮盘，初始 low=0， high=n-1霹俺。mid 表示 [low, high] 的中間位置柔吼。我們通過對比 self[mid] 與value 的大小，來更新接下來要查找的區(qū)間范圍丙唧，直到找到或者區(qū)間縮小為 0愈魏。我就著重強調一下容易出錯的 3 個地方。

1. 循環(huán)退出條件

注意是 low <= high想际，而不是 low < high培漏。

2.mid的取值

實際上，mid=(low+high)/2 這種寫法是有問題的胡本。因為如果low和high比較大的話牌柄，兩者之和就有可能會溢出。改進的方法是將mid的計算方式寫成low+(high- -low)/2侧甫。更進一步珊佣，如果要將性能優(yōu)化到極致的話，我們可以將這里的除以2操作轉化成位運算low+((high-low)>>1)披粟。因為相比除法運算來說彩扔，計算機處理位運算要快得多。

3.low和high的更新

low=mid+1, high=mid-1僻爽。注意這里的+1和-1,如果直接寫成low=mid或者high=mid,就可能,會發(fā)生死循環(huán)虫碉。比如，當high=3, low=3 時胸梆，如果a[3]不等于value,就會導致一直循環(huán)不退出敦捧。

如果你留意我剛講的這三點，我想一個簡單的二分查找你已經可以實現了碰镜。實際上兢卵，二分查找除了用循環(huán)來實現，還可以用遞歸來實現绪颖，過程也非常簡單秽荤。

- (NSInteger)gly_bsearchWithRecursion:(NSString *)propertyName value:(double)value
{
    return [self gly_bsearchInternally:propertyName value:value low:0 high:self.count - 1];
}

- (NSInteger)gly_bsearchInternally:(NSString *)propertyName value:(double)value low:(NSInteger)low high:(NSInteger)high
{
    if (low > high)
    {
        return -1;
    }
    
    //因為相比除法運算來說，計算機處理位運算要快得多。這里也等同于（NSInteger mid = low + (high - low) / 2）
    NSInteger mid = low + ((high - low) >> 1);
    double middleNumber = [[self[mid] valueForKey:propertyName] doubleValue];
    if ([@(middleNumber) compare:@(value)] == NSOrderedSame)
    {
        return mid;
    }
    else if ([@(middleNumber) compare:@(value)] == NSOrderedAscending)
    {
        return [self gly_bsearchInternally:propertyName value:value low:mid + 1 high:high];
    }
    else
    {
        return [self gly_bsearchInternally:propertyName value:value low:low high:mid - 1];
    }
}

二分查找應用場景的局限性

前面我們分析過窃款，二分查找的時間復雜度是O(logn),查找數據的效率非常高课兄。不過，并不是什么情況下都可以用二分查找晨继，它的應用場景是有很大局限性的烟阐。那什么情況下適合用二分查找，什么情況下不適合呢?

首先紊扬，二分查找依賴的是順序表結構蜒茄，簡單點說就是數組。

那二分查找能否依賴其他數據結構呢?比如鏈表餐屎。答案是不可以的檀葛，主要原因是二分查找算法需要按照下標隨機訪問元素。我們在數組和鏈表那兩節(jié)講過腹缩，數組按照下標隨機訪問數據的時間復雜度是0(1)驻谆，而鏈表隨機訪問的時間復雜度是O(n)。所以庆聘，如果數據使用鏈表存儲，- -分查找的時間復雜就會變得很高勺卢。

二分查找只能用在數據是通過順序表來存儲的數據結構上伙判。如果你的數據是通過其他數據結構存儲的，則無法應用二分查找黑忱。

其次宴抚，二分查找針對的是有序數據。

二分查找對這一點的要求比較苛刻甫煞，數據必須是有序的菇曲。如果數據沒有序，我們需要先排序抚吠。前面章節(jié)里我們講到常潮，排序的時間復雜度最低O(nlogn)，所以楷力，如果我們針對的是-組靜態(tài)的數據喊式，沒有頻繁地插入、刪除萧朝，我們可以進行一次排序岔留，多次二分查找。這樣排序的成本可被均攤,二分查找的邊際成本就會比較低检柬。

但是献联，如果我們的數據集合有頻繁的插入和刪除操作，要想用二分查找，要么每次插入里逆、刪除操作之后保證數據仍然有序进胯，要么在每次二分查找之前都先進行排序。針對這種動態(tài)數據集合运悲，無論哪種方法龄减，維護有序的成本都是很高的。

所以班眯，二分查找只能用在插入希停、刪除操作不頻繁，一次排序多次查找的場景中署隘。針對動態(tài)變化的數據集合宠能，二分查找將不再適用。那針對動態(tài)數據集合磁餐，如何在其中快速查找某個數據呢?別急违崇，等到二叉樹那一節(jié)我會詳細講。

再次诊霹，數據量太小不適合二分查找羞延。

如果要處理的數據量很小，完全沒有必要用二分查找脾还，順序遍歷就足夠了伴箩。比如我們在一個大小為10的數組中查找一個元素，不管用二分查找還是順序遍歷鄙漏，查找速度都差不多嗤谚。只有數據量比較大的時候，二分查找的優(yōu)勢才會比較明顯怔蚌。

不過巩步，這里有一個例外。如果數據之間的比較操作非常耗時桦踊，不管數據量大小椅野，我都推薦使用二分查找。比如籍胯，數組中存儲的都是長度超過300的字符串鳄橘，如此長的兩個字符串之間比對大小，就會非常耗時芒炼。我們需要盡可能地減少比較次數瘫怜，而比較次數的減少會大大提高性能，這個時候二分查找就比順序遍歷更有優(yōu)勢本刽。

最后鲸湃，數據量太大也不適合二分查找赠涮。

二分查找的底層需要依賴數組這種數據結構，而數組為了支持隨機訪問的特性暗挑，要求內存空間連續(xù)笋除，對內存的要求比較苛刻。比如炸裆，我們有1GB大小的數據垃它，如果希望用數組來存儲，那就需要1GB的連續(xù)內存空間烹看。

注意這里的“連續(xù)”二字国拇，也就是說，即便有2GB的內存空間剩余惯殊，但是如果這剩余的2GB內存空間都是零散的酱吝，沒有連續(xù)的1GB大小的內存空間，那照樣無法申請一個1GB大小的數組土思。而我們的二分查找是作用在數組這種數據結構之上的务热，所以太大的數據用數組存儲就比較吃力了，也就不能用二分查找了己儒。

但是崎岂，上面介紹的只是最簡單的一種二分查找的代碼實現。接下來我們來講幾種二分查找的變形問題闪湾。

你可能會說冲甘，我們上面學的二分查找的代碼實現并不難寫啊。那是因為上面講的只是二分查找中最簡單的一種情況响谓，在不存在重復元素的有序數組中，查找值等于給定值的元素省艳。最簡單的二分查找寫起來確實不難娘纷，但是，二分查找的變形問題就沒那么好寫了跋炕。

二分查找的變形問題很多赖晶，我只選擇幾個典型的來講解，其他的你可以借助我今天講的思路自己來分析辐烂。

image.png

變體一：查找第一個值等于給定值的元素

前面中的二分查找是最簡單的一種遏插，即有序數據集合中不存在重復的數據，我們在其中查找值等于某個給定值的數據纠修。如果我們將這個問題稍微修改下胳嘲，有序數據集合中存在重復的數據，我們希望找到第一個值等于給定值的數據扣草，這樣之前的二分查找代碼還能繼續(xù)工作嗎?

比如下面這樣一個有序數組了牛，其中颜屠，a[5], a[6]， a[7] 的值都等于8,是重復的數據鹰祸。我們希望查找第一個等于8的數據甫窟，也就是下標是5的元素。

image.png

如果我們用前面講的二分查找的代碼實現蛙婴，首先拿8與區(qū)間的中間值a[4]比較粗井，8比6大，于是在下標5到9之間繼續(xù)查找街图。下標5和9的中間位置是下標7,a[7]正好等于8浇衬，所以代碼就返回了。

盡管a[7]也等于8,但它并不是我們想要找的第一個等于8的元素台夺，因為第一個值等于8的元素是數組下標為5的元素径玖。我們前面講的二分查找代碼就無法處理這種情況了。所以颤介，針對這個變形問題梳星，我們可以稍微改造一下前面的代碼。

100個人寫二分查找就會有100種寫法滚朵。網上有很多關于變形二分查找的實現方法冤灾，有很多寫得非常簡潔，比如下面這個寫法辕近。但是韵吨，盡管簡潔，理解起來卻非常燒腦移宅，也很容易寫錯归粉。

- (NSInteger)gly_bsearchFirstItemWithLoop:(NSString *)propertyName value:(double)value
{
    NSInteger low = 0;
    NSInteger high = self.count - 1;
    
    while (low <= high)
    {
        //為什么不寫(low + high) / 2，是因為如果 low 和 high 比較大的話漏峰，兩者之和就有可能會溢出糠悼。
        NSInteger mid = low + ((high - low) >> 1);
        double middleNumber = [[self[mid] valueForKey:propertyName] doubleValue];
        if ([@(middleNumber) compare:@(value)] == NSOrderedDescending)
        {
            high = mid - 1;
        }
        else if ([@(middleNumber) compare:@(value)] == NSOrderedAscending)
        {
            low = mid + 1;
        }
        else
        {
            if (mid == 0 || [@([[self[mid - 1] valueForKey:propertyName] doubleValue]) compare:@(value)] != NSOrderedSame)
            {
                return mid;
            }
            else
            {
                high = mid - 1;
            }
        }
    }
    
    return -1;
}

我來稍微解釋一下這段代碼。self[mid] 跟要查找的value的大小關系有三種情況:大于浅乔、小于倔喂、等于。對于self[mid]>value的情況靖苇，我們需要更新high= mid-1;對于self[mid]<value的情況席噩，我們需要更新low=mid+1。這兩點都很好理解贤壁。那當self[mid]=value的時候應該如何處理呢?

如果我們查找的是任意一個值等于給定值的元素悼枢，當self[mid]等于要查找的值時，self[mid] 就是我們要找的元素脾拆。但是萧芙，如果我們求解的是第一個值等于給定值的元素给梅，當self[mid]等于要查找的值時，我們就需要確認一下這個self[mid]是不是第一個值等于給定值的元素双揪。

我們重點看一下if (mid == 0 || [@([[self[mid - 1] valueForKey:propertyName] doubleValue]) compare:@(value)] != NSOrderedSame)动羽。如果mid等于0，那這個元素已經是數組的第一個元素渔期，那它肯定是我們要找的;如果mid不等于0,但self[mid]的前一個元素self[mid-1]不等于value,那也說明self[mid]就是我們要找的第一個值等于給定值的元素运吓。

如果經過檢查之后發(fā)現self[mid]前面的一個元素self[mid-1]也等于value,那說明此時的self[mid]肯定不是我們要查找的第一一個值等于給定值的元素。那我們就更新high=mid-1,因為要找的元素肯定出現在[low, mid-1]之間疯趟。

對比上面的兩段代碼拘哨，是不是下面那種更好理解?實際上，很多人都覺得變形的二分查找很難寫,主要原因是太追求第一種那樣完美信峻、簡潔的寫法倦青。而對于我們做工程開發(fā)的人來說，代碼易讀懂盹舞、沒Bug,其實更重要产镐，所以我覺得第二種寫法更好。

變體二：查找最后一個值等于給定值的元素

前面的問題是查找第一個值等于給定值的元素踢步，我現在把問題稍微改一下癣亚，查找最后一個值等于給定值的元素，又該如何做呢获印？如果你掌握了前面的寫法述雾，那這個問題你應該很輕松就能解決。你可以先試著實現一下兼丰，然后跟我寫的對比一下玻孟。

- (NSInteger)gly_bsearchLastItemWithLoop:(NSString *)propertyName value:(double)value
{
    NSInteger low = 0;
    NSInteger high = self.count - 1;
    
    while (low <= high)
    {
        //為什么不寫(low + high) / 2，是因為如果 low 和 high 比較大的話鳍征，兩者之和就有可能會溢出黍翎。
        NSInteger mid = low + ((high - low) >> 1);
        double middleNumber = [[self[mid] valueForKey:propertyName] doubleValue];
        if ([@(middleNumber) compare:@(value)] == NSOrderedDescending)
        {
            high = mid - 1;
        }
        else if ([@(middleNumber) compare:@(value)] == NSOrderedAscending)
        {
            low = mid + 1;
        }
        else
        {
            if (mid == self.count - 1 || [@([[self[mid + 1] valueForKey:propertyName] doubleValue]) compare:@(value)] != NSOrderedSame)
            {
                return mid;
            }
            else
            {
                low = mid + 1;
            }
        }
    }
    
    return -1;
}

我們還是重點看第11行代碼。如果a[mid]這個元素已經是數組中的最后一個元素了蟆技，那它肯定是我們要找的;如果a[mid]的后一個元素a[mid+1]不等于value,那也說明a[mid]就是我們要找的最后一個值等于給定值的元素玩敏。

如果我們經過檢查之后斗忌，發(fā)現a[mid]后面的一個元素a[mid+1]也等于value,那說明當前的這個a[mid]并不是最后一個值等于給定值的元素质礼。我們就更新low=mid+1,因為要找的元素肯定出現在[mid+1, high]之間。

變體三:查找第一個大于等于給定值的元素

現在我們再來看另外- -類變形問題织阳。在有序數組中眶蕉，查找第一個大于等于給定值的元素。比如唧躲，數組中存儲的這樣一個序列: 3, 4造挽，6碱璃，7, 10。如果查找第一個大于等于5的元素饭入，那就是6嵌器。

實際上，實現的思路跟前面的那兩種變形問題的實現思路類似谐丢，代碼寫起來甚至更簡潔爽航。

- (NSInteger)gly_bsearchMoreWithLoop:(NSString *)propertyName value:(double)value
{
    NSInteger low = 0;
    NSInteger high = self.count - 1;
    
    while (low <= high)
    {
        NSInteger mid = low + ((high - low) >> 1);
        double middleNumber = [[self[mid] valueForKey:propertyName] doubleValue];
        if ([@(middleNumber) compare:@(value)] == NSOrderedAscending)
        {
            low = mid + 1;
        }
        else
        {
            if (mid == 0 || [@([[self[mid - 1] valueForKey:propertyName] doubleValue]) compare:@(value)] == NSOrderedAscending)
            {
                return mid;
            }
            else
            {
                high = mid - 1;
            }
        }
    }
    
    return -1;
}

如果self[mid]小于要查找的值value,那要查找的值肯定在[mid+1, high]之間，所以乾忱，我們更新low=mid+1讥珍。

對于self[mid]大于等于給定值value的情況，我們要先看下這個self[mid]是不是我們要找的第一個值大于等于給定值的元素窄瘟。如果a[mid]前面已經沒有元素衷佃，或者前面一個元素小于要查找的值value,那self[mid]就是我們要找的元素。這段邏輯對應的代碼是if (mid == 0 || [@([[self[mid - 1] valueForKey:propertyName] doubleValue]) compare:@(value)] == NSOrderedAscending)這行蹄葱。

如果self[mid-1]也大于等于要查找的值value,那說明要查找的元素在[low, mid-1]之間氏义，所以,我們將high更新為mid-1。

變體四:查找最后一個小于等于給定值的元素

現在新蟆，我們來看最后一種二分查找的變形問題觅赊，查找最后一個小于等于給定值的元素。比如琼稻，數組中存儲了這樣一組數據: 3, 5, 6, 8, 9, 10吮螺。最后一一個小于等于7的元素就是6。是不是有點類似上面那一種?實際上帕翻，實現思路也是一樣的鸠补。

有了前面的基礎，你完全可以自己寫出來了嘀掸，所以我就不詳細分析了紫岩。我把代碼貼出來，你可以寫完之后對比一下睬塌。

- (NSInteger)gly_bsearchLessWithLoop:(NSString *)propertyName value:(double)value
{
    NSInteger low = 0;
    NSInteger high = self.count - 1;
    
    while (low <= high)
    {
        NSInteger mid = low + ((high - low) >> 1);
        double middleNumber = [[self[mid] valueForKey:propertyName] doubleValue];
        if ([@(middleNumber) compare:@(value)] == NSOrderedDescending)
        {
            high = mid - 1;
        }
        else
        {
            if (mid == self.count - 1 || [@([[self[mid + 1] valueForKey:propertyName] doubleValue]) compare:@(value)] == NSOrderedDescending)
            {
                return mid;
            }
            else
            {
                low = mid + 1;
            }
        }
    }
    
    return -1;
}

內容小結

前面我說過泉蝌，凡是用二分查找能解決的，絕大部分我們更傾向于用散列表或者二叉查找樹揩晴。即便是二分查找在內存使用上更節(jié)省勋陪，但是畢竟內存如此緊缺的情況并不多。那二分查找真的沒什么用處了嗎?

實際上硫兰，前面講的求“值等于給定值”的二分查找確實不怎么會被用到诅愚，二分查找更適合用在“近似”查找問題，在這類問題上劫映，二分查找的優(yōu)勢更加明顯违孝。比如今天講的這幾種變體問題刹前，用其他數據結構，比如散列表雌桑、二叉樹喇喉，就比較難實現了。

變體的二分查找算法寫起來非常燒腦校坑，很容易因為細節(jié)處理不好而產生Bug轧飞，這些容易出錯的細節(jié)有:終止條件、區(qū)間上下界更新方法撒踪、返回值選擇过咬。所以今天的內容你最好能用自己實現一遍，對鍛煉編碼能力制妄、邏輯思維掸绞、寫出Bug free代碼，會很有幫助耕捞。

最后：

自己寫了一個NSArray+GLYLookup算法分類衔掸，只需1行代碼，即可完成快速查找俺抽。