?作者簡(jiǎn)介：人工智能專業(yè)本科在讀，喜歡計(jì)算機(jī)與編程，寫博客記錄自己的學(xué)習(xí)歷程。
🍎個(gè)人主頁：小嗷犬的個(gè)人主頁
🍊個(gè)人網(wǎng)站：小嗷犬的技術(shù)小站
🥭個(gè)人信條：為天地立心，為生民立命，為往圣繼絕學(xué)，為萬世開太平。

---

---

簡(jiǎn)介

bisect 庫是 Python 標(biāo)準(zhǔn)庫中的一部分，它提供了二分查找的功能。二分查找是一種在有序列表中查找某一特定元素的搜索算法。它的時(shí)間復(fù)雜度為 $O(\log n)$，比順序查找的時(shí)間復(fù)雜度 $O(n)$ 要有效率。

bisect 庫的使用

bisect 庫提供了 bisect_left、bisect_right、insort_left、insort_right四個(gè)函數(shù)，用于在有序列表中查找或插入元素。

bisect_left

bisect_left 函數(shù)用于在有序列表中二分查找某一位置，使得在該位置插入指定元素后仍保持有序，返回該位置，如果元素已經(jīng)存在，則返回它的左邊位置。

函數(shù)原型如下：

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

其中，a 是一個(gè)有序列表，x 是要查找的元素，lo 和 hi 是查找范圍的左右邊界，key 是一個(gè)函數(shù)，用于從列表中提取比較的鍵值。

示例：

# 導(dǎo)入 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 函數(shù)用于在有序列表中二分查找某一位置，使得在該位置插入指定元素后仍保持有序，返回該位置，如果元素已經(jīng)存在，則返回它的右邊位置。

函數(shù)原型如下：

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

其中，a 是一個(gè)有序列表，x 是要查找的元素，lo 和 hi 是查找范圍的左右邊界，key 是一個(gè)函數(shù)，用于從列表中提取比較的鍵值。

示例：

# 導(dǎo)入 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 還可以簡(jiǎn)寫為 bisect ：

# 導(dǎo)入 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 函數(shù)用于在有序列表中二分查找某一位置，使得在該位置插入指定元素后仍保持有序，然后將元素插入該位置，如果元素已經(jīng)存在，則插入到它的左邊位置。

函數(shù)原型如下：

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

其中，a 是一個(gè)有序列表，x 是要插入的元素，lo 和 hi 是查找范圍的左右邊界，key 是一個(gè)函數(shù)，用于從列表中提取比較的鍵值。

示例：

# 導(dǎo)入 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 函數(shù)用于在有序列表中二分查找某一位置，使得在該位置插入指定元素后仍保持有序，然后將元素插入該位置，如果元素已經(jīng)存在，則插入到它的右邊位置。

函數(shù)原型如下：

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

其中，a 是一個(gè)有序列表，x 是要插入的元素，lo 和 hi 是查找范圍的左右邊界，key 是一個(gè)函數(shù)，用于從列表中提取比較的鍵值。

示例：

# 導(dǎo)入 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 還可以簡(jiǎn)寫為 insort ：

# 導(dǎo)入 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 函數(shù)的實(shí)質(zhì)是調(diào)用 bisect 函數(shù)獲取插入位置，然后調(diào)用 list.insert 函數(shù)將元素插入到該位置。

二分查找基礎(chǔ)實(shí)現(xiàn)

在 Python 中，我們可以使用 bisect 庫來實(shí)現(xiàn)二分查找，但其只能根據(jù)元素的值和元素之間的比較關(guān)系來查找元素的位置，如果要根據(jù)元素的其他屬性或其他關(guān)系來查找元素的位置，就需要自己實(shí)現(xiàn)二分查找了。

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

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

通過修改模板，我們可以根據(jù)更復(fù)雜的關(guān)系來查找元素。

示例：

852. 山脈數(shù)組的峰頂索引
符合下列屬性的數(shù)組 arr 稱為 山脈數(shù)組 ：

• 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]

給你由整數(shù)組成的山脈數(shù)組 arr ，返回任何滿足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下標(biāo) 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, 0while left <= right:mid = (left + right) // 2if arr[mid] > arr[mid + 1]:ans = midright = mid - 1else:left = mid + 1return ans