Python 二分查找之bisect库的使用介绍

蔚落 2024-03-22 20:36 24阅读 0赞

![d9db7c1334e2c59d5be2dbc17f7393ac.jpeg][]

二分查找是一种在有序列表中查找某一特定元素的搜索算法，bisect 库是 Python 标准库中的一部分，它提供了二分查找的功能，这篇文章主要介绍了Python 二分查找之bisect库的使用,需要的朋友可以参考下

### 简介 ###

`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` 函数用于在有序列表中二分查找某一位置，使得在该位置插入指定元素后仍保持有序，返回该位置，如果元素已经存在，则返回它的左边位置。

函数原型如下：

<table> 
 <tbody> 
 <tr> 
 <td> 1 </td> 
 <td> <code>bisect.bisect_left(a, x, lo</code><code>=</code><code>0</code><code>, hi</code><code>=</code><code>len</code><code>(a), </code><code>*</code><code>, key</code><code>=</code><code>None</code><code>)</code> </td> 
 </tr> 
 </tbody> 
</table>

其中，`a` 是一个有序列表，`x` 是要查找的元素，`lo` 和 `hi` 是查找范围的左右边界，`key` 是一个函数，用于从列表中提取比较的键值。

示例：

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 </td> 
 <td> <code># 导入 bisect 库</code> <code>import</code> <code>bisect</code> <code># 有序列表</code> <code>a </code><code>=</code> <code>[</code><code>1</code><code>, </code><code>2</code><code>, </code><code>3</code><code>, </code><code>3</code><code>, </code><code>5</code><code>, </code><code>6</code><code>, </code><code>6</code><code>, </code><code>6</code><code>, </code><code>8</code><code>, </code><code>10</code><code>]</code> <code># 查找元素 4 的位置</code> <code>print</code><code>(bisect.bisect_left(a, </code><code>4</code><code>))&nbsp; </code><code># 4</code> <code># 查找元素 6 的位置</code> <code>print</code><code>(bisect.bisect_left(a, </code><code>6</code><code>))&nbsp; </code><code># 5</code> </td> 
 </tr> 
 </tbody> 
</table>

#### bisect\_right ####

`bisect_right` 函数用于在有序列表中二分查找某一位置，使得在该位置插入指定元素后仍保持有序，返回该位置，如果元素已经存在，则返回它的右边位置。

函数原型如下：

<table> 
 <tbody> 
 <tr> 
 <td> 1 </td> 
 <td> <code>bisect.bisect_right(a, x, lo</code><code>=</code><code>0</code><code>, hi</code><code>=</code><code>len</code><code>(a), </code><code>*</code><code>, key</code><code>=</code><code>None</code><code>)</code> </td> 
 </tr> 
 </tbody> 
</table>

其中，`a` 是一个有序列表，`x` 是要查找的元素，`lo` 和 `hi` 是查找范围的左右边界，`key` 是一个函数，用于从列表中提取比较的键值。

示例：

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 </td> 
 <td> <code># 导入 bisect 库</code> <code>import</code> <code>bisect</code> <code># 有序列表</code> <code>a </code><code>=</code> <code>[</code><code>1</code><code>, </code><code>2</code><code>, </code><code>3</code><code>, </code><code>3</code><code>, </code><code>5</code><code>, </code><code>6</code><code>, </code><code>6</code><code>, </code><code>6</code><code>, </code><code>8</code><code>, </code><code>10</code><code>]</code> <code># 查找元素 4 的位置</code> <code>print</code><code>(bisect.bisect_right(a, </code><code>4</code><code>))&nbsp; </code><code># 4</code> <code># 查找元素 6 的位置</code> <code>print</code><code>(bisect.bisect_right(a, </code><code>6</code><code>))&nbsp; </code><code># 8</code> </td> 
 </tr> 
 </tbody> 
</table>

除此之外，`bisect_right` 还可以简写为 `bisect` ：

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 </td> 
 <td> <code># 导入 bisect 库</code> <code>import</code> <code>bisect</code> <code># 有序列表</code> <code>a </code><code>=</code> <code>[</code><code>1</code><code>, </code><code>2</code><code>, </code><code>3</code><code>, </code><code>3</code><code>, </code><code>5</code><code>, </code><code>6</code><code>, </code><code>6</code><code>, </code><code>6</code><code>, </code><code>8</code><code>, </code><code>10</code><code>]</code> <code># 查找元素 4 的位置</code> <code>print</code><code>(bisect.bisect(a, </code><code>4</code><code>))&nbsp; </code><code># 4</code> <code># 查找元素 6 的位置</code> <code>print</code><code>(bisect.bisect(a, </code><code>6</code><code>))&nbsp; </code><code># 8</code> </td> 
 </tr> 
 </tbody> 
</table>

#### insort\_left ####

`insort_left` 函数用于在有序列表中二分查找某一位置，使得在该位置插入指定元素后仍保持有序，然后将元素插入该位置，如果元素已经存在，则插入到它的左边位置。

函数原型如下：

<table> 
 <tbody> 
 <tr> 
 <td> 1 </td> 
 <td> <code>bisect.insort_left(a, x, lo</code><code>=</code><code>0</code><code>, hi</code><code>=</code><code>len</code><code>(a), </code><code>*</code><code>, key</code><code>=</code><code>None</code><code>)</code> </td> 
 </tr> 
 </tbody> 
</table>

其中，`a` 是一个有序列表，`x` 是要插入的元素，`lo` 和 `hi` 是查找范围的左右边界，`key` 是一个函数，用于从列表中提取比较的键值。

示例：

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 </td> 
 <td> <code># 导入 bisect 库</code> <code>import</code> <code>bisect</code> <code># 有序列表</code> <code>a </code><code>=</code> <code>[</code><code>1</code><code>, </code><code>2</code><code>, </code><code>3</code><code>, </code><code>3</code><code>, </code><code>5</code><code>, </code><code>6</code><code>, </code><code>6</code><code>, </code><code>6</code><code>, </code><code>8</code><code>, </code><code>10</code><code>]</code> <code># 插入元素 4</code> <code>bisect.insort_left(a, </code><code>4</code><code>)</code> <code>print</code><code>(a)&nbsp; </code><code># [1, 2, 3, 3, 4, 5, 6, 6, 6, 8, 10]</code> <code># 插入元素 6</code> <code>bisect.insort_left(a, </code><code>6</code><code>)</code> <code>print</code><code>(a)&nbsp; </code><code># [1, 2, 3, 3, 4, 5, 6, 6, 6, 6, 8, 10]</code> </td> 
 </tr> 
 </tbody> 
</table>

#### insort\_right ####

`insort_right` 函数用于在有序列表中二分查找某一位置，使得在该位置插入指定元素后仍保持有序，然后将元素插入该位置，如果元素已经存在，则插入到它的右边位置。

函数原型如下：

<table> 
 <tbody> 
 <tr> 
 <td> 1 </td> 
 <td> <code>bisect.insort_right(a, x, lo</code><code>=</code><code>0</code><code>, hi</code><code>=</code><code>len</code><code>(a), </code><code>*</code><code>, key</code><code>=</code><code>None</code><code>)</code> </td> 
 </tr> 
 </tbody> 
</table>

其中，`a` 是一个有序列表，`x` 是要插入的元素，`lo` 和 `hi` 是查找范围的左右边界，`key` 是一个函数，用于从列表中提取比较的键值。

示例：

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 </td> 
 <td> <code># 导入 bisect 库</code> <code>import</code> <code>bisect</code> <code># 有序列表</code> <code>a </code><code>=</code> <code>[</code><code>1</code><code>, </code><code>2</code><code>, </code><code>3</code><code>, </code><code>3</code><code>, </code><code>5</code><code>, </code><code>6</code><code>, </code><code>6</code><code>, </code><code>6</code><code>, </code><code>8</code><code>, </code><code>10</code><code>]</code> <code># 插入元素 4</code> <code>bisect.insort_right(a, </code><code>4</code><code>)</code> <code>print</code><code>(a)&nbsp; </code><code># [1, 2, 3, 3, 4, 5, 6, 6, 6, 8, 10]</code> <code># 插入元素 6</code> <code>bisect.insort_right(a, </code><code>6</code><code>)</code> <code>print</code><code>(a)&nbsp; </code><code># [1, 2, 3, 3, 4, 5, 6, 6, 6, 6, 8, 10]</code> </td> 
 </tr> 
 </tbody> 
</table>

除此之外，`insort_right` 还可以简写为 `insort` ：

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 </td> 
 <td> <code># 导入 bisect 库</code> <code>import</code> <code>bisect</code> <code># 有序列表</code> <code>a </code><code>=</code> <code>[</code><code>1</code><code>, </code><code>2</code><code>, </code><code>3</code><code>, </code><code>3</code><code>, </code><code>5</code><code>, </code><code>6</code><code>, </code><code>6</code><code>, </code><code>6</code><code>, </code><code>8</code><code>, </code><code>10</code><code>]</code> <code># 插入元素 4</code> <code>bisect.insort(a, </code><code>4</code><code>)</code> <code>print</code><code>(a)&nbsp; </code><code># [1, 2, 3, 3, 4, 5, 6, 6, 6, 8, 10]</code> <code># 插入元素 6</code> <code>bisect.insort(a, </code><code>6</code><code>)</code> <code>print</code><code>(a)&nbsp; </code><code># [1, 2, 3, 3, 4, 5, 6, 6, 6, 6, 8, 10]</code> </td> 
 </tr> 
 </tbody> 
</table>

`insort` 函数的实质是调用 `bisect` 函数获取插入位置，然后调用 `list.insert` 函数将元素插入到该位置。

### 二分查找基础实现 ###

在 Python 中，我们可以使用 `bisect` 库来实现二分查找，但其只能根据元素的值和元素之间的比较关系来查找元素的位置，如果要根据元素的其他属性或其他关系来查找元素的位置，就需要自己实现二分查找了。

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

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 </td> 
 <td> <code>def</code> <code>binary_search(nums, target):</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>left, right </code><code>=</code> <code>0</code><code>, </code><code>len</code><code>(nums) </code><code>-</code> <code>1</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code> <code>left &lt;</code><code>=</code> <code>right:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>mid </code><code>=</code> <code>(left </code><code>+</code> <code>right) </code><code>/</code><code>/</code> <code>2</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code> <code>nums[mid] </code><code>=</code><code>=</code> <code>target:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>mid</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>elif</code> <code>nums[mid] &lt; target:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>left </code><code>=</code> <code>mid </code><code>+</code> <code>1</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>else</code><code>:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>right </code><code>=</code> <code>mid </code><code>-</code> <code>1</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>-</code><code>1</code> </td> 
 </tr> 
 </tbody> 
</table>

通过修改模板，我们可以根据更复杂的关系来查找元素。

示例：

> **852. 山脉数组的峰顶索引**  
> 符合下列属性的数组 `arr` 称为 **山脉数组** ：

* `arr.length >= 3`
 * 存在 `i`（`0 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

**解**

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 12 </td> 
 <td> <code>class</code> <code>Solution:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>def</code> <code>peakIndexInMountainArray(</code><code>self</code><code>, arr: </code><code>List</code><code>[</code><code>int</code><code>]) </code><code>-</code><code>&gt; </code><code>int</code><code>:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>n </code><code>=</code> <code>len</code><code>(arr)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>left, right, ans </code><code>=</code> <code>1</code><code>, n </code><code>-</code> <code>2</code><code>, </code><code>0</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code> <code>left &lt;</code><code>=</code> <code>right:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>mid </code><code>=</code> <code>(left </code><code>+</code> <code>right) </code><code>/</code><code>/</code> <code>2</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code> <code>arr[mid] &gt; arr[mid </code><code>+</code> <code>1</code><code>]:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>ans </code><code>=</code> <code>mid</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>right </code><code>=</code> <code>mid </code><code>-</code> <code>1</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>else</code><code>:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>left </code><code>=</code> <code>mid </code><code>+</code> <code>1</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>ans</code> </td> 
 </tr> 
 </tbody> 
</table>

到此这篇关于Python 二分查找：bisect库的使用的文章就介绍到这了,希望可以对大家有所帮助。

转自：[微点阅读][Link 1] [https://www.weidianyuedu.com][Link 1]

[d9db7c1334e2c59d5be2dbc17f7393ac.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/51e42601a13a448e9f90ad5a1652adfe.png
[Link 1]: https://www.weidianyuedu.com