简介二分查找算法与相关的Python实现示例_程序人生

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

admin

2023-07-31 02:35:31

0次

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

用Python实现二分查找示例：

>>> def find(self, num):
  l = len(self)
  first = 0
  end = l - 1
  mid = 0
  if l == 0:
   self.insert(0,num)
   return False
  while first < end:
   mid = (first + end)/2
   if num > self[mid]:
    first = mid + 1
   elif num < self[mid]:
    end = mid - 1
   else:
    break
  if first == end:
   if self[first] > num:
    self.insert(first, num)
    return False
   elif self[first] < num:
    self.insert(first + 1, num)
    return False
   else:
    return True
  elif first > end:
   self.insert(first, num)
   return False
  else:
   return True

>>> list_d = [\'a\',\'b\',\'c\',\'d\',\'e\',\'f\',\'d\',\'t\']
>>> value_d = \'t\'
>>> aa=find(list_d,value_d)
>>> aa
True
>>> value_d=\'ha\'
>>> aa=find(list_d,value_d)
>>> aa
False

python 二分查找

上一篇：两个使用Python脚本操作文件的小示例分享

下一篇：Python随手笔记第一篇（2）之初识列表和元组

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

相关内容

热门资讯