Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # coding=utf-8
- """
- bisect实现源码就是**二分查找算法**,**二分查找的对象是:有序数组。这点特别需要注意。要先把数组排好序再操作。**
- **基本步骤:**
- - 从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;
- - 如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。
- - 如果在某一步骤数组为空,则代表找不到。
- 这种搜索算法每一次比较都使搜索范围缩小一半。时间复杂度:**O(logn)**
- 如下源码分析:
- :copyright: (c) 2016 by fangpeng(@beginman.cn).
- :license: MIT, see LICENSE for more details.
- """
- def insort_right(a, x, lo=0, hi=None):
- """在a列表中插入元素x,且保持排序(假设a已经排过序).
- 如果x已经在a中,那么插入到最右边的x的右边.
- 可选参数`lo` (默认 0) and `hi` (默认 `len(a)`列表总长度) 绑定搜索的切片。
- """
- if lo < 0:
- raise ValueError('lo must be non-negative')
- if hi is None:
- hi = len(a)
- while lo < hi:
- mid = (lo+hi)//2 # 取list中间位置
- if x < a[mid]: # 如果x 小于list中间的值,则在前半段继续查找
- hi = mid # hi=mid 将总长度缩短到中间
- else: # 如果x 大于list中间的值,则在后半段继续查找
- lo = mid+1 # lo = mid+1, 起始位置就从中间位置+1处(也就是后半段)开始
- a.insert(lo, x)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement