二分法

1.二分法

①定義：二分查找算法也稱折半搜索算法，對數(shù)搜索算法，是一種在有序數(shù)組中查找某一特定元素的搜索算法。搜索過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結(jié)束；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數(shù)組為空，則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半，時間復(fù)雜度是log(n)

• 一是有序數(shù)組（這里可能是整體有序比如[1,2,3,4,5]，也有可能是局部有序比如[4,5,1,2,3]），
• 二是特定元素（也有可能是滿足特定的條件）。由定義我們大概就知道了二分法的應(yīng)用場景，在有序數(shù)組中找特定值都可以考慮用二分法

②二分法的步驟：

我們要確定一個區(qū)間[L，R]我們要找到一個性質(zhì)（由題目條件決定），并且該性質(zhì)滿足一下兩點： ①滿足二段性 ②答案是二段性的分界點

我們要在一組升序的數(shù)組找一個數(shù)的下標(biāo)，那我們肯定是先拿中間的與他進行比較，比較大小的判斷，其實就相當(dāng)于是這個性質(zhì)，且這個性質(zhì)滿足二段性，將大于和小于我們要查找的值分為兩段，而我們的查找結(jié)果就是分界點

③二分法的使用條件：

①上下界確定 ②區(qū)間內(nèi)有序（也可以是局部有序）

④二分法的目的：

二分查找用于在多條記錄中快速找到待查找的記錄，它的思想是：每次將查找的范圍縮小一半，直到最后找到記錄或者找不到記錄返回

2.引論：猜數(shù)游戲

示例1：

一個 [1, 100] 內(nèi)的數(shù)字，只需猜 7 次：
>50? 是。[1, 100] 二分，中位數(shù) 50，下一步猜 [51, 100]
>75? 否。[51, 100] 二分，中位數(shù) 75，下一步猜 [51, 75]
>63? 否。[51, 75] 二分，...
>56? 否。[51, 63] 二分，
>53? 是。
=54? 是。
這個數(shù)是 54

模板：

	def bin_search(nums)
				low, high = 0, len(nums) - 1
        while low <= high:
            mid = (high - low) // 2 + low
            if num[mid] == target:
                return mid
            elif num[mid] > target:
                high = mid - 1
            else:
                low = mid + 1
        # 未找到目標(biāo)值  
        return -1

思路分析：

二分法題目都可以分下面三步：

1. 確定是否滿足二分法的使用條件 ，有序數(shù)組與查找特定元素，題目中a有序，查找的是指定元素test，滿足條件
2. 確定特定元素test，如：a[pos]=test
3. 確定邊界的變化，根據(jù)定義的第二句話，寫出代碼如下

3.整數(shù)域二分

$mid=(left+right)//2$

$mid=left+(right?left)//2（防止溢出）$

1、在單調(diào)遞增序列中找 x 或者 x 的后繼

• 在單調(diào)遞增數(shù)列 a[ ] 中查找某個數(shù) x，如果數(shù)列中沒有 x，找比它大的下一個數(shù)
• a[mid]>=x 時：x 在 mid 的左邊，新的搜索區(qū)間是左半部分，left不變，更新 right= mid
• a[mid]<x 時：x 在 mid 的右邊，新的搜索區(qū)間是半部分，right不變，更新 left=mid+1
• 代碼執(zhí)行完畢后，$left=right$，兩者相等，即答案所處的位置

def bin_search(a,n,x):  #在數(shù)組a中找數(shù)字x，返回位置
    left=0
    right=n     
    while left<right:
        mid=left+(right-left)//2
        if a[mid]>=x:
            right=mid
        else:
            left=mid+1
        #print('[',left,right,']')   #打印猜數(shù)游戲的過程
    return left

2、在單調(diào)遞增序列中查找 x 或者 x 的前驅(qū)

• 在單調(diào)遞增數(shù)列 a[ ] 中查找某個數(shù) x，如果數(shù)列中沒有 x，找比它小的前一個數(shù)
• a[mid] <= x時，x 在 mid 的右邊，新的搜索區(qū)間是右半部分，所以 right 不變，更新 left=mid
• a[mid] > x時，x 在 mid 的左邊，新的搜索區(qū)間是左半部分，所以left不變，更新 right=mid-1
• 當(dāng) $left=right$ 時，得到結(jié)果

def bin_search(a,n,x):  #在數(shù)組a中找數(shù)字x，返回位置
    left=0
    right=n     
    while left<right:
        mid=left+(right-left+1)//2
        if a[mid]<=x:
            left=mid
        else:
            right=mid-1
        #print('[',left,right,']')   #打印猜數(shù)游戲的過程
    return left

總結(jié)：

1.找后繼——向右對齊，mid = (left+right) // 2 即為將mid盡可能向下取，不超過目標(biāo)數(shù)字，同時，盡可能保證右端不動（左端和右端相等時，即為后繼）

a[mid]≥x : right=mid（右定）

a[mid]<x : left=mid+1

2.找前驅(qū)——向左對齊，mid=left+(right-left+1)//2 即為將mid盡可能向上取，超過目標(biāo)數(shù)字，同時，盡可能保證左端不動（右端和相等時，即為前驅(qū)）

a[mid]≤x : left=mid（左定）

a[mid]>x : right=mid-1

3.簡易二分模板

假設(shè)：L指向check()=True的部分（≤目標(biāo)值），R指向check()=False的部分（＞目標(biāo)值），假設(shè)可以根據(jù)題目需要來確定

二分完成后，L和R分別指向所屬區(qū)域的臨界位置（終止條件:l+1=r）

注意：左端點和右端點的初始化要定義在范圍外，l, r = -1, n + 1

圖解：

標(biāo)準(zhǔn)解題模板：

def check():
    **# check為題目中判斷條件**
    pass
 
def bin_search(a, n, x):
    l, r = -1, n + 1
    while l + 1 != r:
        mid = (l+r) // 2
        if check(mid):
            l = mid
        else:
            r = mid
    return (l or r) # 選取需要的部分進行返回

模板分析：

• 左右指針均指向數(shù)組外，這樣移動時直接使 *l*,r=mid即可——*相當(dāng)于自動完成了+1和-1的操作*
• 返回左邊界，則當(dāng)≤目標(biāo)值時移動 *l* ; 返回右邊界，則當(dāng)≥目標(biāo)值時移動 r
• 終止條件為r=*l*+1 ——*這里相當(dāng)于左閉右開，即此時區(qū)間內(nèi)只有l(wèi)eft對應(yīng)的元素*

示例： 套用這個模板把區(qū)間劃分成≤5和＞5兩塊，返回左邊界：5的最后一個的下標(biāo)

# 把邊界劃分成≤5和＞5兩塊
def bin_search2(a,n,x):
    l,r = -1,n+1
    while l + 1 != r:
        mid = (l+r)//2
        if a[mid]<=x:
            l = mid
        else:
            r = mid
    return l # 返回左邊界
 
a = [1,2,2,3,5,5,5,6,7]
print(bin_search2(a,len(a),5)) # 6 

若想返回5的第一個的下標(biāo)，把區(qū)間劃分成＜5和≥5，返回右邊界r，修改部分代碼即可：

# 將上面的代碼中間修改成這部分代碼
            if a[mid]>=x:
                r = mid
            else:
                l = mid
        return r # 返回右邊界

總結(jié)：

1. 若想保留左邊界，則判斷條件時，當(dāng)nums[mid]==x時就要移動左指針left=mid
2. 若想保留右邊界，則判斷條件時，當(dāng)nums[mid]==x時就要移動右指針right=mid

4.浮點數(shù)二分

浮點數(shù)二分不需要考慮邊界，往往是給定一個精度范圍，讓你在精度范圍中去找到這個數(shù)

step：

1.確定eps:當(dāng)兩數(shù)差小到一定程度是則可認(rèn)為找到數(shù)

一般求到題目要求的精度再加兩個精度，否則特殊案例精度不夠通不過

2.取中間值:double mid=l+（r-l）/2 ——注意這里不是整除

3.二分法：

eps=0.0001     #精度，如果用for，可以不要eps
while right-left>eps:
#for i in range(100):
    mid=left+(right-left)/2
    if check(mid):      **# 判定是否滿足條件**
        right=mid       
    else:
        left=mid

這里left和right均更新為mid，因為存在精度，而一般的整數(shù)域二分精度可以默認(rèn)為0

示例：

[NOIP2001 提高組] 一元三次方程求解 - 洛谷

思路分析：

（二分法是建立在枚舉的基礎(chǔ)上進行的優(yōu)化，所以此類問題往往是先考慮枚舉，再根據(jù)二分法對算法進行優(yōu)化）枚舉**根的值域中的每一個整數(shù)x（-100<=x<=100），由于根與根之差的絕對值>=1，因此設(shè)定搜索區(qū)間[l，r]，其中l(wèi)=x，r=x+1——（設(shè)置二分的區(qū)域往往是一個難點，由題目條件而定）

（0）特判：判斷最右端（100）是否為f（x）的根；
（1）若f（l）==0，則右端點l為f（x）的根；

這里要注意，只選擇判斷左端是因為，若右端也判斷，則會在下一個區(qū)間再次判斷，造成重根

（2）若f（l) * f（r）>0，則確定根x不在區(qū)間[l，r]內(nèi)，設(shè)定[r，r+1]為下一個搜索區(qū)間；
（3）若f（l) * f（r）<0，則確定根x在區(qū)間[l，r]內(nèi)：

如果確定根在區(qū)間[l，r]內(nèi)的話（f（l）*f（r）<0），如何在該區(qū)間找到根的確切位置，采用二分法，將區(qū)間[l，r]分成左右兩個子區(qū)間：左子區(qū)間[l，x]和右子區(qū)間[x，r]：

1. 若f（l）*f（x）<=0，則確定根在左子區(qū)間[l，x] 內(nèi)，將x設(shè)為該區(qū)間的右指針（r=x），繼續(xù)對左子區(qū)間進行對分；
2. 若f（l）*f（x）>0，則確定根在右子區(qū)間（x，r] 內(nèi)，將x設(shè)為該區(qū)間的左指針（l=x），繼續(xù)對右子區(qū)間進行對分；

上述對分過程一直進行到區(qū)間的間距滿足精度要求為止（r-l<0.0001），此時確定l為f（x）的根

枚舉+二分：

# fx表達式
def f(x):
    fx=a*x**3+b*x**2+c*x+d
    return fx

eps=0.001
a,b,c,d=map(float,input().split())
res=[]
# 1.枚舉每一個小區(qū)間
for i in range(-100,100):
    l,r=i,i+1
    y1,y2=f(l),f(r)
    # 1.右端為零點
    if y1==0:
        res.append(l)
    # 2.區(qū)間內(nèi)有零點——不在兩端
    if y1*y2<0:
        # 二分法
        while r-l>eps:
            mid=l+(r-l)/2 # 分左右區(qū)間
            if f(mid)*y1>=0:
                l=mid
            else:
                r=mid
        res.append(l)
    # 4.剪枝優(yōu)化
    if len(res)>=3:
        break
# 特判
if f(100)==0:
    res.append(100)
# 輸出小數(shù)點后兩位數(shù)字
for i in range(3):
    **# print('%.2f'%res[i],end=' 'if i!=2 else '')**
    print("{:.2f}".format(res[i]),end=' 'if i!=2 else '')

• 補充：兩種常用保留小數(shù)點后兩位的方式：

  print(”{:.2f}”.format(num))

  print(”%.2f”.%num)
  
  

5.邊界二分

數(shù)組原本整體有序，之后圍繞某一旋轉(zhuǎn)點變成了局部有序，旋轉(zhuǎn)點即為邊界點

1.旋轉(zhuǎn)數(shù)組

示例：

尋找旋轉(zhuǎn)數(shù)組最小值

力扣

假設(shè)按照 升序排序 的數(shù)組在預(yù)先未知的某個點上進行了旋轉(zhuǎn)。例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,**0,**1,2] ，找到其中最小元素

規(guī)則：
數(shù)組 [a[0], a[1], a[2], ..., a[n-1]] **旋轉(zhuǎn)一次 的結(jié)果為**
數(shù)組 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 

輸入：nums = [4,5,6,7,0,1,2]
輸出：0

思路分析：

1. 確定是否滿足二分法的使用條件：前面數(shù)組都是整體有序，現(xiàn)在變成局部有序了，target是求最小元素，滿足二分條件

2. 確定特定元素target的偽代碼，這題target是唯一個滿足小于后一個數(shù)的（未旋轉(zhuǎn)作為特殊情況），在圖中為nums[4]<nums[3] ——將target抽象即為nums[n-1]<nums[n]，未旋轉(zhuǎn)直接返回nums[0]

3. 確定邊界：局部有序數(shù)組，先看數(shù)組的特點是什么，如果 以旋轉(zhuǎn)點為界分為左右倆個區(qū)間，4是左邊區(qū)間的最小值，2是右邊區(qū)間的最大值，那么根據(jù)這倆個條件就可以確定nums[mid]屬于哪個區(qū)間，即滿足小于左區(qū)間最大值屬于右區(qū)間，大于右區(qū)間最大值屬于左區(qū)間

思路與算法：

（圖片來源于leetcode）

其中橫軸表示數(shù)組元素的下標(biāo)，縱軸表示數(shù)組元素的值。圖中標(biāo)出了最小值的位置，是我們需要查找的目標(biāo)。

我們考慮數(shù)組中的最后一個元素 x：在最小值右側(cè)的元素（不包括最后一個元素本身），它們的值一定都嚴(yán)格小于 x；而在最小值左側(cè)的元素，它們的值一定都嚴(yán)格大于 x。因此，我們可以根據(jù)這一條性質(zhì)，通過二分查找的方法找出最小值。

在二分查找的每一步中，左邊界為 low 右邊界為 high，區(qū)間的中點為 pivot，最小值就在該區(qū)間內(nèi)。我們將中軸元素 nums[pivot]與右邊界元素 nums[high]進行比較，可能會有以下情況：

第一種情況是 nums[pivot]<nums[high]：

如下圖所示，這說明 nums[pivot] 是最小值右側(cè)的元素，因此我們可以忽略二分查找區(qū)間的右半部分

第二種情況是 nums[pivot]>nums[high]：

如下圖所示，這說明 nums[pivot] 是最小值左側(cè)的元素，因此我們可以忽略二分查找區(qū)間的左半部分。

第三種情況是 nums[pivot]=nums[high]：

由于數(shù)組不包含重復(fù)元素，并且只要當(dāng)前的區(qū)間長度不為 1，pivot就不會與 high重合；而如果當(dāng)前的區(qū)間長度為 1，這說明我們已經(jīng)可以結(jié)束二分查找了。因此不會存在 nums[pivot]=nums[high]的情況

		class Solution:
    def findMin(self, nums: list[int]) -> int:
        if nums[0]<nums[1]:
            return nums[0]
        low=0
        high=len(nums)-1
        while low<high:
            mid=low+(high-low)//2
            if nums[mid]<nums[high]:
                high=mid
            else:
                left=mid+1
        return nums[left]

2.開閉區(qū)間

真正影響的是中間那個數(shù)字（mid）到底該不該加入下一次的查找中，也就是邊界問題

二分法最重要的兩個問題：

①while循環(huán)中 left 和 right 的關(guān)系，到底是 left <= right 還是 left < right

②迭代過程中 middle 和 right 的關(guān)系，到底是 right = middle - 1 還是 right = middle

1、每次查找區(qū)間在[left, right]，左閉右閉

① while(left <= right) 因為當(dāng)(left == right)這種情況發(fā)生的時候，得到的結(jié)果是有意義的；左閉右閉對于區(qū)間內(nèi)只有一個值也是有意義的
② if(nums[middle] > target)， right 要賦值為 middle - 1， 因為當(dāng)前的 nums[middle] 一定不是 target ，需要把這個 middle 位置上面的數(shù)字丟棄，那么接下來需要查找范圍就是[left,middle - 1]

def search(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums) - 1
        while low <= high:
            mid = (high - low) // 2 + low
            if num[mid] == target:
                return mid
            elif num[mid] > target:
                high = mid - 1
            else:
                low = mid + 1
        # 未找到目標(biāo)值  
        return -1

2、每次查找區(qū)間在[left, right），左閉右開

①while(left < right)，因為左閉右開對于區(qū)間內(nèi)只有一個值是沒有意義的 ②if(nums[middle] > target)， right = middle ，因為當(dāng)前的 nums[middle] 是大于 target 的，不符合條件,不能取到 middle，并且區(qū)間的定義是 [left, right)，剛好區(qū)間上的定義就取不到 right, 所以 right 賦值為 middle

def search(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums)
        while low < high:   # 區(qū)別1
            mid = (high - low) // 2 + low
            if num[mid] == target:
                return mid
            elif num[mid] < target:
                low = mid + 1
            else:
                high = mid  # 區(qū)別2
        # 未找到目標(biāo)值  
        return -1

如要查找的元素為3，將right = mid寫成了right = mid - 1那么就會出現(xiàn)如下錯誤，3直接錯過了

總結(jié)：Right = nums.length or Right =nums.length-1

情況1：Right = nums.length ; while(left < right) 這種情況下，每一次二分取值mid后，判斷nums[mid]，如果nums[mid] >
target,那么更新右邊界時，必須注意，此時Right = mid;（相當(dāng)于右邊為開區(qū)間） 防止出現(xiàn)[target , mid ,
right]; 更新Right = mid-1;會跳出循環(huán)外，返回值為-1的情況。

情況2：Right = nums.length-1
; while(left <= right) 這種情況下，每一次二分取值mid后，判斷nums[mid]，如果nums[mid] >
target,那么更新右邊界時，必須注意，此時Right = mid - 1 ;（相當(dāng)于右邊為閉區(qū)間）

防止出現(xiàn)left == Right(如果為right=mid),一直在循環(huán)內(nèi)死循環(huán)問題

6.二分法的應(yīng)用

1.優(yōu)化時間復(fù)雜度

示例：

分巧克力

思路分析：

一個個試邊長 d 太慢了，現(xiàn)在使用二分，按前面的“猜數(shù)游戲”的方法猜 d 的取值，即轉(zhuǎn)化為判斷對應(yīng)邊長下長，寬均滿足條件的巧克力數(shù)是否滿足條件

暴力法需要做 d 次 check()， 用二分法，只需要做 O(logd) 次 check()，總復(fù)雜度 O(nlogd)
d∈[1，10^5]

# 檢查半徑是否滿足
def check(d):
    cnt=0
    for i in range(n):
        cnt+=(w[i]//d)*(h[i]//d) **# 長，寬均要滿足**
    if cnt>=k:
        return 1
    else:
        return 0

w=[0]*100010
h=[0]*100010
n,k=map(int,input().split())
for i in range(n):
    w[i],h[i]=map(int,input().split())

l=0
r=100010-1

# 找前驅(qū)
while l<r:
    mid=l+(r-l+1)//2
    if check(mid)!=0:
        l=mid # 左對齊
    else:
        r=mid-1
print(l)

2.最小值最大化

示例：

跳石頭

519. 跳石頭 - AcWing題庫

思路分析：

在 n 塊巖石中移走 m 個石頭，有很多種移動方法。在第 i 種移動方法中，剩下的石頭之間的距離，有一個最小距離 ai

在所有移動方法的最小距離 ai 中，問最大的 ai 是多少。在所有可能的最小值中，找最大的那個，就是 “最小值最大化”

如果用暴力法找所有的組合，在 n 塊巖石中選 m 個石頭的組合情況太多，顯然會超時

二分思路：*不去找搬走石頭的各種組合，而是*給出一個距離d，檢查能不能搬走 m 塊石頭而得到最短距離 d，即轉(zhuǎn)化為判斷對應(yīng)距離下可以搬走的石頭數(shù)是否滿足條件。把所有的 d 都試一遍，肯定能找到一個最短的d，用二分法找這個 d 即可

1. 左指針指向起點，右指針指向終點，進行二分查找得到mid（枚舉的最短距離）

2. 對每一個枚舉的mid(d)進行判斷：

   1. 先令pos為起點，遍歷每一個點——貪心：保證每次操作都是局部最優(yōu)，最終滿足全局最優(yōu)
   2. 如果這個點到pos的距離小于d，則刪去這個石頭，刪去石頭數(shù)cnt+=1
   3. 如果這個點到pos的距離大于等于d，則將pos更新為該石頭
   4. 最后判斷刪去石頭數(shù)是否超過了限定值

   d∈[1，總長]

二分+貪心：

# 3.判斷距離的合法性
def check(d):
    pos=stone[0]
    cnt=0
    for i in range(1,n+1):
        # 1.如果當(dāng)前石頭距離pos的距離小于給定的d
        if stone[i]-pos<d:
            cnt+=1
        else:
            pos=stone[i]
    if cnt<=m:
        return 1
    else:
        return 0

l,n,m=map(int,input().split())
# 1.構(gòu)造stone 表示相較于起點的距離
stone=[0]*(n+2)
stone[0]=0
stone[n+1]=l
for i in range(1,n+1):
    stone[i]=int(input())

# 2.對可能的距離二分查找---最小值最大化
l,r=0,l
while l<r:
    mid=l+(r-l+1)//2
    if check(mid)!=0:
        l=mid  # 限定最小左邊界
    else:
        r=mid-1
print(l)

二分法模板題——最小最大化問題：

• 找最小值的最大化：相當(dāng)于每找到一個合法值就限定左邊界，為向左看齊：

  mid=left+(right-left+1)//2

  if 滿足條件:

  left=mid

  else:

  right=mid-1

• 找最大值的最小化：相當(dāng)于每找到一個合法值就限定右邊界，為向右看齊：

  mid=left+(right-left)//2

  if 滿足條件:

  right=mid

  else:

  left=mid+1
  
  

3.最大值最小化

示例：

青蛙過河

思路分析：

• 因為要使跳躍距離≤d，又要使d最小，為最大值的最小化，則考慮二分

1. 首先要理解一個問題：

   往返累計2x次等效于單獨去2x次

   原因：實際上轉(zhuǎn)化一下，怎么去就怎么回，所以其實就是和去2x次一模一樣

2. 接下來，考慮對跳躍距離d在區(qū)間內(nèi)進行二分：

   $l$ 指向最小跳躍距離為1，r 指向最大跳躍距離為n（總寬度）

   ①若mid合法——即能跳過去，則減少跳躍能力

   ②若mid不合法——即跳不過去，則增加跳躍能力

3. 最關(guān)鍵的是判斷合法性的check函數(shù)：

• 首先，要考慮青蛙應(yīng)該怎么跳過去，由貪心，青蛙每次都跳自己能力極限的距離為最優(yōu)，這樣才盡可能保證讓石頭剩下的高度足夠

• 其次，考慮怎么判斷合法性：

  • 第一種做法：可以暴力枚舉，即每一個點和下一個目標(biāo)位置點，下一個目標(biāo)位置點可以用二分查找

  • 第二種做法：

    充要條件：

    所有長度為 mid 的區(qū)間的和都大于等于 2x <—>則一定能走2x次

思路：由于往返可以等效，我們可以看作是2x只青蛙同時在過河，若劃分為以mid為長度的k個區(qū)間，則所有青蛙必定會經(jīng)過各個mid區(qū)間1次，即每個區(qū)間都會被走過2x次，所以要使都能走過去，一定要讓每一個mid區(qū)間內(nèi)高度和大于2x

實現(xiàn)：所以，用sum記錄每一個點到起點之間的高度總和，當(dāng)給定一個mid時，以i為終點（mid≤i≤總長），區(qū)間長為mid，則該區(qū)間內(nèi)的高度和即為sum[i]-sum[i-mid]，遍歷每一個區(qū)間，判斷其是否大于2x即可，時間復(fù)雜度為O（n）

def check(d):
    for i in range(mid,n):    # 遍歷以i-mid為起點的每一個區(qū)間
        if sum[i]-sum[i-mid]<2*x: # 若存在區(qū)間長度小于2x 跳不過去
            return 0
    return 1

n,x=map(int,input().split())
# 記錄石頭的高度
s_high=list(map(int,input().split()))
# 記錄區(qū)間石頭的高度和 起點高度和為0
sum=[0,s_high[0]]
for i in range(1,len(s_high)):
    sum.append(s_high[i]+sum[i])

# 二分法
l,r=1,n # 跳躍能力區(qū)間
while l<r:
    mid=l+(r-l)//2
    if check(mid):
        r=mid # 能跳過去 減少跳躍能力
    else:
        l=mid+1 # 跳不過去 增加跳躍能力
print(r)

7.總結(jié)

? ?本篇主要講解了二分法的一些表示及其用法，同樣后面也有一些相應(yīng)的實例，后續(xù)還會更新其他常見的算法，如果有錯誤請歡迎指正~~，感謝?。。?br>

覺得本篇有幫助的話, 就賞個三連吧~

文章來源地址http://www.zghlxwxcb.cn/news/detail-703982.html

到了這里，關(guān)于【算法】—二分法詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！