「@Author：Runsen」

?

編程的本質(zhì)來源于算法，而算法的本質(zhì)來源于數(shù)學(xué)，編程只不過將數(shù)學(xué)題進(jìn)行代碼化。「---- Runsen」

?

二分法查找

有的人也許說二分查找很簡單，確實思路很簡單，但細(xì)節(jié)是魔鬼。

?

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky…

?

翻譯成：「雖然二進(jìn)制搜索的基本思想相對簡單，但細(xì)節(jié)可能會令人驚訝地棘手」

算法：當(dāng)數(shù)據(jù)量很大適宜采用該方法。采用二分法查找時，數(shù)據(jù)需是「有序不重復(fù)」的。二分法查找本質(zhì)上就是分治算法。

分治算法是把一個復(fù)雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題 直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。

二分查找的也稱為折半查找，由于每次都能夠?qū)⒉檎覅^(qū)間縮小為原來一半，這種算法的時間復(fù)雜度為。

基本思想：假設(shè)數(shù)據(jù)是按升序排序的，對于給定值 x，從序列的中間位置開始比較，如果當(dāng)前位置值等于 x，則查找成功；若 x 小于當(dāng)前位置值，則在數(shù)列的前半段中查找；若 x 大于當(dāng)前位置值則在數(shù)列的后半段中繼續(xù)查找，直到找到為止。

二分法查找就是查找一個數(shù)組元素的下標(biāo)。定義兩個變量，一個low，一個high，則mid=(low+high)/2。

算法核心中有三種情況：

• 如果value==arr[mid]，中間值正好要查找的值，則返回下標(biāo)，return mid;

• 如果valuehigh=mid-1;

• 如果value>arr[mid]，要找的值大于中間的值，則再往數(shù)組的大端找，low=mid+1;

下面代碼就是二分查找的Python代碼表述。我注釋寫清楚了。

'''
@Author：Runsen
@WeChat：RunsenLiu 
@微信公眾號：Python之王
@CSDN：https://blog.csdn.net/weixin_44510615
@Github：https://github.com/MaoliRUNsen
@Date：2020/9/7

標(biāo)準(zhǔn)的二分查找

題目：給定n個元素，這些元素是有序的（假定為升序），使用二分法從中查找特定的元素。
要求：輸入n個元素，輸入某一個特定的值m，首先對n個元素進(jìn)行排序（排序算法任選），輸出m值的位置序號。
'''

def?binary_search(list,?num):
????left?=?0
????right?=?len(list)?-?1??#?注意1?low和right用于跟蹤在其中查找的列表部分
????while?left?<=?right:??#?注意2?只要還沒有縮小到只有一個元素，就不停的檢查
????????mid?=?(left?+?right)?//?2
????????if?list[mid]?==?num:
????????????return?mid
????????elif?list[mid]?>?num:
????????????right?=?mid?-?1??#?注意3?猜的數(shù)字大了
????????elif?list[mid]?????????????left?=?mid?+?1???#?注意4?猜的數(shù)字小了
????return?mid


A?=?[1,?4,?2,?5,?3,?7,?8]
num?=?5
A?=?sorted(A)??#?python?內(nèi)置排序是快速排序
print(A)
print(binary_search(A,?num))

[1,?2,?3,?4,?5,?7,?8]
4

二分查找的變形問題

二分查找難在變形問題，這里我主要寫的四種常見的二分變形問題。

圖來自爭大佬while low <= high:和mid = low + ((high - low) >> 1)基本在四個變形固定了。然后就是通過分析位置進(jìn)行判斷什么時候就返回，（需要注意端點(diǎn)取值的情況），然后就是判斷往右移動還是往左移動，小于等于，大于等于，道理都是一樣。

寫文章的日子是大四上學(xué)的第一天，天氣還OK，大四竟然寫了四種二分算法的變種都寫對，都是看爭哥算法專欄的效果，真的牛逼，妥妥的光頭強(qiáng)。

突然間感到二分算法的變種問題，其實很簡單了。

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

變形一：「查找第一個等于給定值的元素。特點(diǎn)，存在重復(fù)值?！?/strong>

下面找到排序數(shù)組中target第一次出現(xiàn)的位置為例，也是二分最常見的變形。

比如nums= [1,2,2,3,3,3,4,4,5], target=4, return 6。

target在數(shù)組中的值，return返回的是第一個等于給定值的index。

注意點(diǎn)：while low <= high: 需要 <=

mid = low + ((high - low) >> 1) 最好用位運(yùn)算，比//2 好，防止泄露。

小了：說明要往右移動：low = mid + 1

大了：說明要往左移動：high = mid - 1

時刻要注意：端點(diǎn)的情況

求第一個等于定值：需要對等于的情況進(jìn)行判斷，如果是端點(diǎn) mid == 0或者該值前面一個不等于該值nums[mid-1] != target，直接return。否則就是在該值前面一個也等于該值的情況，需要往左移動high = mid - 1。

def?bsearch_left(nums,target):
????'''求第一個等于定值?'''
????low?=?0
????high?=?len(nums)?-?1
????#?這里需要?<=
????while?low?<=?high:
????????#?這里需要注意：?就是使用((high - low)?>> 1)需要雙擴(kuò)號
????????mid?=?low?+?((high?-?low)?>>?1)
????????if?nums[mid]?????????????low?=?mid?+?1
????????elif?nums[mid]?>?target:
????????????high?=?mid?-?1
????????else:
????????????if?mid?==?0?or?nums[mid-1]?!=?target:
????????????????return?mid
????????????else:
????????????????high?=?mid?-1

????return?-1

nums=?[1,2,2,3,3,3,4,4,5]
target=4
print(bsearch_left(nums,target))?#6

查找最后一個等于給定值的元素

比如nums= [1,2,2,3,3,3,4,4,5], target=4, return 7。

target在數(shù)組中的值，return返回的是最后一個等于給定值的index。

注意點(diǎn)：while low <= high: 需要 <=

mid = low + ((high - low) >> 1) 最好用位運(yùn)算，比//2 好，防止泄露。

小了：說明要往右移動：low = mid + 1

大了：說明要往左移動：high = mid - 1

時刻要注意：端點(diǎn)的情況

求最后一個等于給定值：需要對等于的情況進(jìn)行判斷，如果是端點(diǎn) mid == (len(nums) -1)或者該值后面一個不等于該值nums[mid] != nums[mid+1]，直接return。否則就是在該值后面面一個也等于該值的情況，需要往右移動low = mid +1。

def?bsearch_right(nums,target):
????'''求最后一個等于定值的'''
????low?=?0
????higt?=?len(nums)?-1
????while?low?<=?higt:
????????mid?=?low?+?((higt-?low)?>>1?)
????????if?nums[mid]?>?target:
????????????higt?=?mid?-?1
????????elif?nums[mid]?????????????low?=?mid?+1
????????else:
????????????if?mid?==?(len(nums)?-1)?or?nums[mid]?!=?nums[mid+1]:
????????????????return?mid
????????????else:
????????????????low?=?mid?+1
????return??-1
????
????
nums=?[1,2,2,3,3,3,4,4,5]
target=4
print(bsearch_right(nums,target))?#7

下面LeetCode 第 34題：在排序數(shù)組中查找元素的第一個和最后一個位置，手到擒來。

也就是查找第一個等于給定值的元素和查找最后一個等于給定值的元素的結(jié)合

#給定一個按照升序排列的整數(shù)數(shù)組 nums，和一個目標(biāo)值 target。找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置。?
#?你的算法時間復(fù)雜度必須是 O(log n)?級別。?
#?如果數(shù)組中不存在目標(biāo)值，返回?[-1,?-1]
#?示例?1:
#?輸入:?nums?=?[5,7,7,8,8,10],?target?=?8
#輸出:?[3,4]?
#?示例?2:?
#?輸入:?nums?=?[5,7,7,8,8,10],?target?=?6
#輸出:?[-1,-1]?
#?Related?Topics?數(shù)組?二分查找


class?Solution:
????def?searchrightRange(self,nums:?List[int],target:?int)?->int:
????????lefts,rights?=?0,len(nums)-1
????????while??lefts?<=?rights:
????????????mid?=?(lefts+rights)//2
????????????if??nums[mid]?>?target:
????????????????rights?=?mid-1
????????????elif????nums[mid]?????????????????lefts?=?mid+1
????????????else:
????????????????lefts?=?mid+1
????????if??lefts-1?>=?0?and?nums[lefts-1]?==?target:
????????????return??lefts-1
????????else:
????????????return??-1?
????def?searchleftRange(self,nums:?List[int],target:?int)?->int:
????????lefts,rights?=?0,len(nums)-1
????????while???lefts?<=?rights:
????????????mid?=?(lefts+rights)//2
????????????if??nums[mid]?>?target:
????????????????rights?=?mid-1
????????????elif??nums[mid]?????????????????lefts?=?mid+1
????????????else:
????????????????rights?=?mid-1
????????if??rights+1?and?nums[rights+1]?==?target:
????????????return??rights+1
????????else:
????????????return??-1
????def?searchRange(self,?nums:?List[int],?target:?int)?->?List[int]:
????????if??len(nums)?==?0:
????????????return??[-1,-1]
????????rights?=?self.searchrightRange(nums,target)
????????lefts?=?self.searchleftRange(nums,target)
????????return??[lefts,rights]

第一個大于等于目標(biāo)值的下標(biāo)（數(shù)組中可能不存在目標(biāo)值）

比如nums= [3,4,6,7,19], target=5, return 2。

時刻要注意：端點(diǎn)的情況。思路：如果nums[mid] >= target，說明返回的值在nums[mid]或者nums[mid]前面兩者之一，因此需要再判斷nums[mid - 1] < target。如果nums[mid - 1] > target，需要往左移動。如果nums[mid] < target，需要往右移動。

'''
查找第一個大于等于給定值的元素
*?如序列：3，4，6，7，19 查找第一個大于5的元素，即為6，return 2
*?第一個大于給定值，則說明上一個小于給定值，依次判斷
'''
def?bsearch_left_not_less(nums,target):
????low?=?0
????high?=?len(nums)?-1
????while(low<=high):
????????mid?=?low?+?((high-low)?>>1)
????????if?nums[mid]?>=?target:
????????????if?mid?==?0?or?nums[mid?-?1]?????????????????return?mid
????????????else:
????????????????#?往左移動
????????????????high?=?mid?-?1
????????else:
????????????#?往右移動
????????????low?=?mid?+1
????return?-1
print(bsearch_left_not_less([3,4,6,7,19],5))
#?2

最后一個小于等于目標(biāo)值的下標(biāo)（數(shù)組中可能不存在目標(biāo)值）

比如nums= [3,4,6,7,19], target=5, return 1。

時刻要注意：端點(diǎn)的情況。思路：如果nums[mid] <= target，說明返回的值在nums[mid]或者nums[mid]后面兩者之一，因此需要再判斷nums[mid + 1] > target。如果nums[mid + 1] > target，需要往右移動。如果nums[mid] > target，需要往左移動。

'''
查找第一個小于給定值的元素
*?如序列：3，4，6，7，19 查找第一個小于5的元素，即為4，返回1
*?第一個大于給定值，則說明上一個小于給定值，依次判斷
'''
def?bsearch_right_not_greater(nums,target):
????'''求最后一個小于等于值'''
????low?=?0
????higt?=?len(nums)?-1
????while?low?<=?higt:
????????mid?=?low?+?((?higt?-low?)?>>?1)
????????if?nums[mid]?<=?target:
????????????if?(mid?==?len(nums)?-1)?or?(nums[mid?+?1]?>?target):
????????????????return?mid
????????????else:
????????????????low?=?mid?+1
????????else:
????????????higt?=?mid?-1
????return??-1
print(bsearch_right_not_greater([3,4,6,7,19],5))
#?1

感悟：順利寫出四個二分變種問題的解法，寫了四種二分算法的變種，竟然都寫對，這還是我嗎？如果在算法題中遇到二分，絕對不手軟。

「人生最重要的不是所站的位置，而是內(nèi)心所朝的方向。只要我在每篇博文中寫得自己體會，修煉身心；在每天的不斷重復(fù)學(xué)習(xí)中，耐住寂寞，練就真功，不畏艱難，奮勇前行，不忘初心，砥礪前行，人生定會有所收獲，不留遺憾 （作者：Runsen ）」

?

本文已收錄 GitHub，傳送門~^[1] ，里面更有大廠面試完整考點(diǎn)，歡迎 Star。

?