纯净、安全、绿色的下载网站

首页|软件分类|下载排行|最新软件|IT学院

当前位置:首页IT学院IT技术

python二分法查找 python二分法查找实例代码

栾沫   2021-11-21 我要评论
想了解python二分法查找实例代码的相关内容吗,栾沫在本文为您仔细讲解python二分法查找的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:python二分查找,python二分法查找程序,Python二分法查找算法,下面大家一起来学习吧。

对于要搜索的元素越多,二分查找速度比简单查找快的更多 这是二分查找算法的优点,但二分算法也有缺点,二分算法只针对有序的列表,这样插入和删除就会很困难,因此,折半查找方法只适合不经常变动的有序列表

 二分查找有个很重要的特点,就是不会查找数列的全部元素,而查找的数据量其实正好符合元素的对数,正常情况下每次查找的元素都在一半一半地减少。所以二分查找的时间复杂度为 O(log2n) 是毫无疑问的。当然,最好的情况是只查找一次就能找到,但是在最坏和一般情况下的确要比顺序查找好了很多。

题目一:给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target  ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
class Solution:
    def search(self,nums:List[int],target:int)->int:
        left=0
        right=len(nums)-1
        while(left<=right):
            mid=(left+right)//2
            if nums[mid]==target:
               return mid
            if nums[mid]<target:
                left=mid+1
            else:
                right=mid-1
        return -1
题目二:在一个严格递减的数组中,找到第二个比目标值target大的数的下标。若不存在,则返回-1。 
class Solution:
    def search(self,nums:List[int],target:int)->int:
        left=0
        right=len(nums)-1
        while(left<=right):
            mid=(left+right)//2
            if nums[mid]==target:
               return mid
            if nums[mid]>target:
                left=mid+1
            else:
                right=mid-1
        return -1
题目三:函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ,所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复使用相同的元素。
class Solution:
     def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i in range(len(numbers)-1):
            left=i
            right=len(numbers) - 1
            while(left<=right):
                mid=(left+right)//2
                if numbers[mid]+numbers[i]==target:
                    return [i+1,mid+1]
                elif numbers[mid]+numbers[i]<target:
                    left=mid+1
                else:
                    right = mid-1
            return [-1,-1]

总结


相关文章

猜您喜欢

  • Vue之监听数据的原理 Vue之监听数据的原理详解

    想了解Vue之监听数据的原理详解的相关内容吗,王同学要努力在本文为您仔细讲解Vue之监听数据的原理的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:Vue详解,Vue监听数据的原理,下面大家一起来学习吧。..
  • Vue之事件处理和事件修饰符 Vue之事件处理和事件修饰符详解

    想了解Vue之事件处理和事件修饰符详解的相关内容吗,王同学要努力在本文为您仔细讲解Vue之事件处理和事件修饰符的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:Vue事件处理,Vue事件修饰符,下面大家一起来学习吧。..

网友评论

Copyright 2020 www.mwhsoft.com 【绿色软件站】 版权所有 软件发布

声明:所有软件和文章来自软件开发商或者作者 如有异议 请与本站联系 点此查看联系方式