⼆分查
⼆分查也称为是折半查，属于有序查算法。元素必须是有序的，如果是⽆序的则要先进⾏排序操作。⼆分查的前提条件是需要有序表顺序存储，对于静态查表，⼀次排序后不再变化，⼆分查能得到不错的效率。但对于需要频繁执⾏插⼊或删除操作的数据集来说，维护有序的排序会带来不⼩的⼯作量，那就不建议使⽤。 原理：
弹性纤维⼆分查⽤给定值k先与中间结点的关键字⽐较，中间结点把线形表分成两个⼦表，若相等则查成功；若不相等，再根据k与该中间结点关键字的⽐较结果确定下⼀步查哪个⼦表，这样递归进⾏，直到查到或查结束发现表中没有这样的结点。
算法详细描述：
选择⼀个可以将列表arr⼤致⼀份为⼆的索引i；
检查是否有arr[i] == target；
如果不是，检查arr[i]⼤于还是⼩于target；望乡词
根据上⼀步的结果，确定在arr的左半部分还是右半部分搜索target。
代码实现：
## 递归版本
def binarySearch(arr, target):
"""
假设arr是列表，其中元素按升序排列.
一般等价物如果target是arr中的元素，则返回True，否则返回False
"""
def bSearch(arr, target, low, high):
if high == low:
return arr[low] == target
mid = (low + high) // 2
if arr[mid] == target:
return True
elif arr[mid] > target:
if low == mid:
return False
else:
return bSearch(arr, target, low, mid - 1)
else:
return bSearch(arr, target, mid + 1, high)
if len(arr) == 0:
return False
else:
return bSearch(arr, target, 0, len(arr) - 1)
## ⾮递归版本
def binarySearch(arr, target):
low = 0
high = len(arr) - 1
while low < high:
mid = (low + high) // 2
if target < arr[mid]:
high = mid - 1溢价能力
elif target > arr[mid]:
low = mid + 1
else:
return True
除铁剂return False
时间复杂度：
楔形体假设，总共有n个元素，每次查的区间⼤⼩就是n，n/2，n/4，…，n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。由于n/2^k取整后>=1，即令n/2^k=1，可得k=log2n,（是以2为底，n的对数），所以时间复杂度可以表⽰O()=O(logn)
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议