用Python实现一个二分查找的函数

发布时间:2022-04-15 10:05:35 人气:62 作者:多测师

  二分查找算法:简单的说,就是将一个列表先排序好,比如按照从小到大的顺序排列好,当给定一个数据,比如3,查找3在列表中的位置时,可以先找到列表中间的数li[middle]和3进行比较,当它比3小时,那么3一定是在列表的右边,反之,则3在列表的左边,比如它比3小,则下次就可以只比较[middle+1, end]的数,继续使用二分法,将它一分为二,直到找到3这个数返回或者列表全部遍历完成(3不在列表中)

  优点:效率高,时间复杂度为O(logN);

  缺点:数据要是有序的,顺序存储。

用Python实现一个二分查找的函数

  li = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

  def search(someone, li):

  l = -1

  h = len(li)

  while l + 1 != h:

  m = int((l + h) / 2)

  if li[m] < someone:

  l = m

  else:

  h = m

  p = h

  if p >= len(li) or li[p] != someone:

  print("元素不存在")

  else:

  str = "元素索引为%d" % p

  print(str)

  search(3, li) # 元素索引为2

  以上内容为大家介绍了用Python实现一个二分查找的函数,希望对大家有所帮助,如果想要了解更多Python相关知识,请关注多测师。https://www.e70w.com/xwzx/


返回列表
在线客服
联系方式

热线电话

17727591462

上班时间

周一到周五

二维码
线