Python 二分查詢之bisect庫的使用詳解

2023-03-13 06:00:14

簡介

bisect 庫是 Python 標準庫中的一部分，它提供了二分查詢的功能。二分查詢是一種在有序列表中查詢某一特定元素的搜尋演演算法。它的時間複雜度為 O ( log ⁡ n ) O(log n) O(logn)，比順序查詢的時間複雜度 O ( n ) O(n) O(n) 要有效率。

bisect 庫的使用

bisect 庫提供了 bisect_left、bisect_right、insort_left、insort_right四個函數，用於在有序列表中查詢或插入元素。

bisect_left

bisect_left 函數用於在有序列表中二分查詢某一位置，使得在該位置插入指定元素後仍保持有序，返回該位置，如果元素已經存在，則返回它的左邊位置。

函數原型如下：

bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)

其中，a 是一個有序列表，x 是要查詢的元素，lo 和 hi 是查詢範圍的左右邊界，key 是一個函數，用於從列表中提取比較的鍵值。

範例：

# 匯入 bisect 庫
import bisect
# 有序列表
a = [1, 2, 3, 3, 5, 6, 6, 6, 8, 10]
# 查詢元素 4 的位置
print(bisect.bisect_left(a, 4))  # 4
# 查詢元素 6 的位置
print(bisect.bisect_left(a, 6))  # 5

bisect_right

bisect_right 函數用於在有序列表中二分查詢某一位置，使得在該位置插入指定元素後仍保持有序，返回該位置，如果元素已經存在，則返回它的右邊位置。

函數原型如下：

bisect.bisect_right(a, x, lo=0, hi=len(a), *, key=None)

其中，a 是一個有序列表，x 是要查詢的元素，lo 和 hi 是查詢範圍的左右邊界，key 是一個函數，用於從列表中提取比較的鍵值。

範例：

# 匯入 bisect 庫
import bisect
# 有序列表
a = [1, 2, 3, 3, 5, 6, 6, 6, 8, 10]
# 查詢元素 4 的位置
print(bisect.bisect_right(a, 4))  # 4
# 查詢元素 6 的位置
print(bisect.bisect_right(a, 6))  # 8

除此之外，bisect_right 還可以簡寫為 bisect ：

# 匯入 bisect 庫
import bisect
# 有序列表
a = [1, 2, 3, 3, 5, 6, 6, 6, 8, 10]
# 查詢元素 4 的位置
print(bisect.bisect(a, 4))  # 4
# 查詢元素 6 的位置
print(bisect.bisect(a, 6))  # 8

insort_left

insort_left 函數用於在有序列表中二分查詢某一位置，使得在該位置插入指定元素後仍保持有序，然後將元素插入該位置，如果元素已經存在，則插入到它的左邊位置。

函數原型如下：

bisect.insort_left(a, x, lo=0, hi=len(a), *, key=None)

其中，a 是一個有序列表，x 是要插入的元素，lo 和 hi 是查詢範圍的左右邊界，key 是一個函數，用於從列表中提取比較的鍵值。

範例：

# 匯入 bisect 庫
import bisect
# 有序列表
a = [1, 2, 3, 3, 5, 6, 6, 6, 8, 10]
# 插入元素 4
bisect.insort_left(a, 4)
print(a)  # [1, 2, 3, 3, 4, 5, 6, 6, 6, 8, 10]
# 插入元素 6
bisect.insort_left(a, 6)
print(a)  # [1, 2, 3, 3, 4, 5, 6, 6, 6, 6, 8, 10]

insort_right

insort_right 函數用於在有序列表中二分查詢某一位置，使得在該位置插入指定元素後仍保持有序，然後將元素插入該位置，如果元素已經存在，則插入到它的右邊位置。

函數原型如下：

bisect.insort_right(a, x, lo=0, hi=len(a), *, key=None)

其中，a 是一個有序列表，x 是要插入的元素，lo 和 hi 是查詢範圍的左右邊界，key 是一個函數，用於從列表中提取比較的鍵值。

範例：

# 匯入 bisect 庫
import bisect
# 有序列表
a = [1, 2, 3, 3, 5, 6, 6, 6, 8, 10]
# 插入元素 4
bisect.insort_right(a, 4)
print(a)  # [1, 2, 3, 3, 4, 5, 6, 6, 6, 8, 10]
# 插入元素 6
bisect.insort_right(a, 6)
print(a)  # [1, 2, 3, 3, 4, 5, 6, 6, 6, 6, 8, 10]

除此之外，insort_right 還可以簡寫為 insort ：

# 匯入 bisect 庫
import bisect
# 有序列表
a = [1, 2, 3, 3, 5, 6, 6, 6, 8, 10]
# 插入元素 4
bisect.insort(a, 4)
print(a)  # [1, 2, 3, 3, 4, 5, 6, 6, 6, 8, 10]
# 插入元素 6
bisect.insort(a, 6)
print(a)  # [1, 2, 3, 3, 4, 5, 6, 6, 6, 6, 8, 10]

insort 函數的實質是呼叫 bisect 函數獲取插入位置，然後呼叫 list.insert 函數將元素插入到該位置。

二分查詢基礎實現

在 Python 中，我們可以使用 bisect 庫來實現二分查詢，但其只能根據元素的值和元素之間的比較關係來查詢元素的位置，如果要根據元素的其他屬性或其他關係來查詢元素的位置，就需要自己實現二分查詢了。

二分查詢的基本模板如下：

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

通過修改模板，我們可以根據更復雜的關係來查詢元素。

範例：

852. 山脈陣列的峰頂索引
符合下列屬性的陣列 arr 稱為 山脈陣列 ：

arr.length >= 3
存在 i（0 < i < arr.length - 1）使得：
- arr[0] < arr[1] < ... arr[i-1] < arr[i]
- arr[i] > arr[i+1] > ... > arr[arr.length - 1]

給你由整陣列成的山脈陣列 arr ，返回任何滿足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下標 i 。

來源：力扣（LeetCode）
連結：https://leetcode.cn/problems/peak-index-in-a-mountain-array

解

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        n = len(arr)
        left, right, ans = 1, n - 2, 0
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] > arr[mid + 1]:
                ans = mid
                right = mid - 1
            else:
                left = mid + 1
        return ans

到此這篇關於Python 二分查詢：bisect庫的使用的文章就介紹到這了,更多相關Python bisect庫使用內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

Python 二分查詢之bisect庫的使用詳解

目錄

簡介

bisect 庫的使用

bisect_left

bisect_right

insort_left

insort_right

二分查詢基礎實現

熱門文章