Python中bisect的用法

本文实例讲述了Python中bisect的用法,是一个比较常见的实用技巧。分享给大家供大家参考。具体分析如下:

一般来说,Python中的bisect用于操作排序的数组,比如你可以在向一个数组插入数据的同时进行排序。下面的代码演示了如何进行操作:

import bisect
import random
random.seed(1)
print('New pos contents')
print('-----------------')
l=[]

for i in range(1,15):
  r=random.randint(1,100)
  position=bisect.bisect(l,r)
  bisect.insort(l,r)
  print '%3d %3d'%(r,position),l

输出结果为:

New pos contents
-----------------
 14  0 [14]
 85  1 [14, 85]
 77  1 [14, 77, 85]
 26  1 [14, 26, 77, 85]
 50  2 [14, 26, 50, 77, 85]
 45  2 [14, 26, 45, 50, 77, 85]
 66  4 [14, 26, 45, 50, 66, 77, 85]
 79  6 [14, 26, 45, 50, 66, 77, 79, 85]
 10  0 [10, 14, 26, 45, 50, 66, 77, 79, 85]
 3  0 [3, 10, 14, 26, 45, 50, 66, 77, 79, 85]
 84  9 [3, 10, 14, 26, 45, 50, 66, 77, 79, 84, 85]
 44  4 [3, 10, 14, 26, 44, 45, 50, 66, 77, 79, 84, 85]
 77  9 [3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]
 1  0 [1, 3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]

可以看到,在插入这些随机数的时候数组同时进行了排序。不过其中有一些重复的元素,比如上面的77,77。你可以对这些重复元素的顺序进行设置,如果希望重复的元素出现在与他相同的元素左边就是用bisect_left,否则就是用bisect_right,相应的使用insort_left和insort_right。比如下面的代码,我们可以看到出现重复的元素索引变化:

import bisect
import random
random.seed(1)
print('New pos contents')
print('-----------------')
l=[]

for i in range(1,15):
  r=random.randint(1,100)
  position=bisect.bisect_left(l,r)
  bisect.insort_left(l,r)
  print '%3d %3d'%(r,position),l

输出结果为:

New pos contents
-----------------
 14  0 [14]
 85  1 [14, 85]
 77  1 [14, 77, 85]
 26  1 [14, 26, 77, 85]
 50  2 [14, 26, 50, 77, 85]
 45  2 [14, 26, 45, 50, 77, 85]
 66  4 [14, 26, 45, 50, 66, 77, 85]
 79  6 [14, 26, 45, 50, 66, 77, 79, 85]
 10  0 [10, 14, 26, 45, 50, 66, 77, 79, 85]
 3  0 [3, 10, 14, 26, 45, 50, 66, 77, 79, 85]
 84  9 [3, 10, 14, 26, 45, 50, 66, 77, 79, 84, 85]
 44  4 [3, 10, 14, 26, 44, 45, 50, 66, 77, 79, 84, 85]
 77  8 [3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]
 1  0 [1, 3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]

此函数bisect.bisect(list,key) ,犹如java里的TreeMap的tailMap(fromkey)。

希望本文所述对大家的Python程序设计有所帮助。

(0)

相关推荐

  • Python 字符串操作实现代码(截取/替换/查找/分割)

    Python 截取字符串使用 变量[头下标:尾下标],就可以截取相应的字符串,其中下标是从0开始算起,可以是正数或负数,下标可以为空表示取到头或尾. 复制代码 代码如下: # 例1:字符串截取str = '12345678'print str[0:1]>> 1   # 输出str位置0开始到位置1以前的字符print str[1:6]  >> 23456   # 输出str位置1开始到位置6以前的字符num = 18str = '0000' + str(num) # 合并字符串pr

  • 简介二分查找算法与相关的Python实现示例

    二分查找Binary Search的思想: 以有序表表示静态查找表时,查找函数可以用二分查找来实现. 二分查找(Binary Search)的查找过程是:先确定待查记录所在的区间,然后逐步缩小区间直到找到或找不到该记录为止. 1二分查找的时间复杂度是O(log(n)),最坏情况下的时间复杂度是O(n). 假设 low 指向区间下界,high 指向区间上界,mid 指向区间的中间位置,则 mid  = (low + high) / 2; 具体过程: 1.先将关键字与 mid 指向的元素比较,如果相

  • Python实现二分查找与bisect模块详解

    前言 其实Python 的列表(list)内部实现是一个数组,也就是一个线性表.在列表中查找元素可以使用 list.index() 方法,其时间复杂度为O(n) .对于大数据量,则可以用二分查找进行优化. 二分查找要求对象必须有序,其基本原理如下: 1.从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束: 2.如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较. 3.如果在某一步骤数组为空,则代表找不到. 二分查找也

  • python中bisect模块用法实例

    本文实例讲述了python中bisect模块用法,分享给大家供大家参考. 具体方法分析如下: 这个模块只有几个函数,一旦决定使用二分搜索时,立马要想到使用这个模块. 示例代码如下: import bisect L = [1,3,3,6,8,12,15] x = 3 x_insert_point = bisect.bisect_left(L,x)#在L中查找x,x存在时返回x左侧的位置,x不存在返回应该插入的位置..这是3存在于列表中,返回左侧位置1 print x_insert_point x_

  • Python字符串中查找子串小技巧

    惭愧啊,今天写了个查找子串的Python程序被BS了- 如果让你写一个程序检查字符串s2中是不是包含有s1.也许你会很直观的写下下面的代码: 复制代码 代码如下: #determine whether s1 is a substring of s2 def isSubstring1(s1,s2):     tag = False     len1 = len(s1)     len2 = len(s2)     for i in range(0,len2):         if s2[i] =

  • Python二分查找详解

    先来看个实例 #!/usr/bin/env python import sys def search2(a,m): low = 0 high = len(a) - 1 while(low <= high): mid = (low + high)/2 midval = a[mid] if midval < m: low = mid + 1 elif midval > m: high = mid - 1 else: print mid return mid print -1 return -

  • python二分查找算法的递归实现方法

    本文实例讲述了python二分查找算法的递归实现方法.分享给大家供大家参考,具体如下: 这里先提供一段二分查找的代码: def binarySearch(alist, item): first = 0 last = len(alist)-1 found = False while first<=last and not found: midpoint = (first + last)//2 if alist[midpoint] == item: found = True else: if ite

  • Python基于二分查找实现求整数平方根的方法

    本文实例讲述了Python基于二分查找实现求整数平方根的方法.分享给大家供大家参考,具体如下: x=int(raw_input('please input a int:')) if x<0: retrun -1 low=0 high=x ans=(low+high)/2.0 sign=ans while ans**2 !=x: if ans**2>x: high=ans else: low=ans ans=(low+high)/2.0 if sign==ans: break print ans

  • python实现在目录中查找指定文件的方法

    本文实例讲述了python实现在目录中查找指定文件的方法.分享给大家供大家参考.具体实现方法如下: 1. 模糊查找 复制代码 代码如下: import os from glob import glob #用到了这个模块 def search_file(pattern, search_path=os.environ['PATH'], pathsep=os.pathsep):     for path in search_path.split(os.pathsep):         for mat

  • Python实现二分查找算法实例

    本文实例讲述了Python实现二分查找算法的方法.分享给大家供大家参考.具体实现方法如下: #!/usr/bin/env python import sys def search2(a,m): low = 0 high = len(a) - 1 while(low <= high): mid = (low + high)/2 midval = a[mid] if midval < m: low = mid + 1 elif midval > m: high = mid - 1 else:

随机推荐