Python二分法

本文將詳細介紹Python中的二分法的實現方法及其應用場景。

一、二分法簡介

二分法，又叫二分查找法，是一種在有序數組中查找目標值的算法，其基本思想是將目標值與有序數組的中間值進行比較，根據比較的結果可以確定目標值位於數組的哪一部分。通過不斷縮小查找範圍，最終找到目標值或者確定不存在。

在Python中，二分法是一種高效的算法，運用廣泛。例如在圖像處理、數據分析、數值計算等領域都有着廣泛的應用。

二、Python實現二分法

下面是Python實現二分法查找的模板代碼：

def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

二分法的關鍵在於將搜索範圍不斷縮小，這裡通過left和right兩個指針來完成。在每次循環中，計算出中間值mid，通過與目標值的比較來確定目標值所在的區間，並繼續縮小區間，直至找到目標值。

三、二分法應用場景

二分法可以解決許多實際問題，下面介紹幾個常見的應用場景。

1、尋找數值的峰值

在一個數組中，峰值指的是一個數既大於它左側的數，也大於它右側的數。使用二分法查找數值的峰值：

def find_peak_element(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[mid + 1]:
            right = mid
        else:
            left = mid + 1
    return left

2、尋找有序數組中的目標值範圍

在一個有序數組中，尋找目標值的範圍可以使用二分法查找左右兩個邊界。

def search_range(nums, target):
    left, right = 0, len(nums) - 1
    left_bound, right_bound = -1, -1
    # 找左邊界
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            right = mid - 1
            left_bound = mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    # 找右邊界
    left, right = left_bound, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            left = mid + 1
            right_bound = mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return [left_bound, right_bound]

3、尋找旋轉排序數組中的目標值

在一個旋轉的有序數組中，尋找目標值可以使用二分法查找。

def search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:  # 左半邊有序
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # 右半邊有序
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

四、總結

本文主要介紹了Python中的二分法，包括二分法的概念、Python實現二分法的代碼模板，以及二分法的應用場景。從數值峰值的查找到目標值範圍的尋找，再到旋轉排序數組的查找，二分法無處不在，運用廣泛。掌握了二分法的基本思想和代碼實現，對於Python編程工程師來說是至關重要的。