python – 在列表中查找.这可以在O(log n)中完成吗？

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python – 在列表中查找.这可以在O(log n)中完成吗？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1407字，纯文字阅读大概需要3分钟。

内容图文

我有一个整数列表,我试图通过使用递归算法来识别整数列表中的倾角来实现O(log n).下降是紧随其后并且遵循等于或大于其自身的数字的任何数字,并且遵循,使得x> = dip <= y.只要它们旁边的数字大于或等于这些元素,就可以将第一个和最后一个元素视为倾角. 我已经能够通过简单地遍历列表来实现O(n),但是我正在尝试使用类似于二进制搜索算法的方法来实现更快的结果.我只需要在列表中找到一个下降点. 我的问题是当我将列表分成中点的左侧和右侧时,我最终会使用一个/两个元素到达较小的列表,但它们不一定是坑,因为它们没有考虑到它们切片之外的数字. 谁能帮我？

def find_dip(lst):
     if len(lst) == 1:
          return 0
     elif len(lst) == 2:
          if lst[0] <= lst[1]:
               return 0
          else:
               return 1
     else:
          ans = False
          mid = len(lst) // 2
          print("test")
          if lst[mid-1] >= lst[mid] <= lst[mid+1]:
               ans = mid
          elif ans == False and len(lst[mid:]) > 2:
               if lst[mid] >= lst[mid+1] <= lst[mid+2]:
                    ans = mid+1
          elif ans == False and len(lst[:mid]) > 2:
               if lst[mid-2] >= lst[mid-1] <= lst[mid]:
                    ans = mid-1      
          elif ans == False:
               ans = find_dip(lst[:mid])
          else:
               ans = find_dip(lst[mid+1:])
          return ans

解决方法:

答案是肯定的.基于以下link发现峰值(与倾角完全相反)需要O(log n)时间.但是差异是肤浅的,所描述的算法可以以完全相似的方式进行调整.这是一个python版本：

def find_dip(lst):
    start, end = 0, len(lst) - 1
    while start < end:
        if end - start == 1: return start if lst[start] <= lst[end] else end
        mid = (start + end) / 2
        a, b, c = lst[mid - 1: mid + 2]
        if a >= b <= c: return mid
        if a <= b: end = mid - 1
        else: start = mid + 1
    return end

内容总结

以上是互联网集市为您收集整理的python – 在列表中查找.这可以在O(log n)中完成吗？全部内容，希望文章能够帮你解决python – 在列表中查找.这可以在O(log n)中完成吗？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端