二分搜索?Binary Search

視頻一：二分查找，一個(gè)視頻搞定！【基礎(chǔ)算法精講 04】

視頻二：搜索旋轉(zhuǎn)排序數(shù)組【基礎(chǔ)算法精講 05】

????關(guān)于有序數(shù)組中的二分查找及其衍生題，我一直覺得麻煩的不是思想，而是細(xì)節(jié)。leetcode比賽分?jǐn)?shù)上不去，和OJ大佬相比，不是題目做少的問題，而是缺少沉下心來反思和總結(jié)。這兩天剛好看到靈神的基礎(chǔ)算法系列視頻，想著最近也沒啥事，反芻一下順便寫個(gè)筆記。

????二分的模版一般有三種：有全閉區(qū)間的[left, right]，左閉右開的[left, right)，還有全開區(qū)間的(left, right)。每一種特點(diǎn)不同，循環(huán)里判斷條件也不同，很看個(gè)人口味。我比較懶，覺得模版太多比較煩，也記不住，第二種最通用，所以我比較喜歡，以后碰到相關(guān)的題基本都按照這個(gè)套路寫。力扣33題是一道使用二分的基礎(chǔ)題，這里寫了之后配合靈神的講解視頻，記錄下幾個(gè)比較有用的點(diǎn)：

????- 要點(diǎn)一：

????????轉(zhuǎn)化，>, <, <= 啥的都可以轉(zhuǎn)化為 >=，比如找數(shù)組中?>x 的元素開始位置：lower_bound(a, target+1)；找 <x? 的元素結(jié)束位置：lower_bound(a, target) -1；找 <=x 的元素結(jié)束位置：lower_bound(a, target+1) -1；

????- 要點(diǎn)二：

????????二是用左開右閉的時(shí)候一般都要后處理，因?yàn)榭赡苷也坏缴兜?，這里循環(huán)結(jié)束時(shí)肯定是left==right，所以到底選left還是right也不用為難了，隨便拉一個(gè)判定下答案符不符合要求就行了，少了麻煩

????- 要點(diǎn)三：

????????二分要是一般用java/c++/golang啥的可能在取mid時(shí)候會(huì)溢出，可以這樣寫 mid = left + (right-left)/2，但我刷題一般用python哈哈哈

????這道題我也是用[left, right)左閉右開寫的，因?yàn)檫@道題肯定有答案所以不用后置處理。而且這里題目里數(shù)全是不同的，所以已經(jīng)很方便了，不需要額外多處理。這里 nums[mid] < nums[right] 寫成 nums[mid] < nums[-1] 也是可以的，反正就是通過對(duì)比mid處的數(shù)和另一個(gè)數(shù)，這個(gè)數(shù)只要能夠幫助二分就行。

????這題是153的進(jìn)階，多了一個(gè)數(shù)組中的數(shù)字可以重復(fù)，所以最壞情況下退化為線性搜索，沒了O(log n)的效率，不過這不是啥問題。

????- 要點(diǎn)一

????????注意這里因?yàn)閿?shù)字可以重復(fù)，所以要是找原數(shù)組最右邊的數(shù)字nums[-1]比較不行了，因?yàn)楫?dāng) nums[mid] == nums[-1] 時(shí)，需要去掉mid和right指向的兩個(gè)重復(fù)數(shù)字中的一個(gè)（因?yàn)楸Ａ粢粋€(gè)就等于也保留了這個(gè)數(shù)是答案的可能），這里用腳想也知道不能去掉mid，所以只能去掉right指向的那個(gè)數(shù)，不然循環(huán)就推進(jìn)不下去了。而right一變，要是下次比較還和nums[-1]比，那就錯(cuò)了。

????這里主要是多了個(gè)mid和mid+1兩個(gè)數(shù)的比較，一般題目就是用到mid，所以用到mid+1時(shí)可能會(huì)溢出，這里把right在初始化的時(shí)候-1，這樣的話，之要進(jìn)了while循環(huán)，里面的mid和mid+1就肯定是合法的，不用擔(dān)心下標(biāo)非法。至于本題答案是肯定存在的，所以不需要后處理。

????這題吧，兩次二分和一次二分都行。不過感覺靈神這種一次二分的處理更好更有意思，之后把二分判定邏輯寫成函數(shù)肯定更通用，所以更偏向于第二種解。另外視頻里靈神是用全開區(qū)間，即 (left, right)，所以初始化和中間指針的時(shí)候會(huì)和我的不一樣，不過我還是喜歡我自己這種，無所謂了。

總結(jié)：

????二分感覺還是挺搞的，細(xì)節(jié)比較多，比較煩，但這么一梳理，感覺還行，以后就用左閉右開模版了 [left, right)。希望下次遇到相似的題不再怵了。