首页 > 编程语言 >Python高级之【补充】算法

Python高级之【补充】算法

时间:2024-05-09 15:25:05浏览次数:29  
标签:target nums Python 高级 mid 算法 查找 data left

【一】二分法

【1】介绍

  • 二分法也称为折半法,是一种在有序数组中查找特定元素的搜索算法

【2】思路

  • 首先,从数组的中间元素开始搜索,如果该元素正好是目标元素,则搜索过程结束,否则执行下一步
  • 如果目标元素大于/小于中间元素,则在数组大于/小于中间元素的那一半区域查找,然后重复步骤的操作
  • 如果某一步数组为空,则表示找不到目标元素

【3】模版

(1)查找指定数

  • 查找指定数是指只需要查找出指定数在数组中的索引即可,并不规定指定数在数组中所处的相对位置
def binary_Search(nums, target):
    left, right = 0, len(nums) - 1  # 搜索区间两边为闭
    while left <= right:  # 注意停止条件,停止条件为[left, left+1]
        mid = (right + left) // 2
        # 找到指定数并返回其索引
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1  # 因为mid已经搜索过
        else:
            right = mid - 1
    return -1


nums = [1, 8, 9, 7, 4, 5, 3, 1, 6]
target = 6
result = binary_Search(nums, target)
print(result)  # 8
# 6所在的索引位置正是 8
  • 此处要注意的是:
  • while循环的条件left <= right代表中止条件为[left, left+1]
  • 如果不加等号,则中止条件为[left,left]此时life并没有被搜索,是不正确的

(2)左边界查找

  • 左边界查找是指需要查找出指定数在数组中第一次出现的位置的索引
def left_Search(nums, target):
    left, right = 0, len(nums) - 1  # 搜索区间两边为闭
    while left <= right:
        mid = (right + left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    if left >= len(nums) or nums[left] != target:
        return -1
    return left


nums = [1, 8, 9, 7, 4, 5, 3, 1, 6]
target = 6
result = left_Search(nums, target)
print(result)  # 8
# 6所在的索引位置正是 8
  • 此处要注意的是:
  • 主要是要理解左边界查找和查找指定数的区别,在查找指定数时nums[mid] == target表示已经找到指定数,则返回该数索引即为结果
  • 而在左边界查找时nums[mid] == target并不能表示已经得到结果,因为我们不知道这个数是不是最左边的,所以当nums[mid] == target时我们要将右边界设置为mid - 1,再次进行循环

(3)右边界查找

  • 右边界查找跟左边界类似,只不过右边界需要的是查找出最后一次出现的位置的索引
def left_Search(nums, target):
    left, right = 0, len(nums) - 1  # 搜索区间两边为闭
    while left <= right:
        mid = (right + left) // 2
        if nums[mid] <= target:
            left = mid + 1
        else:
            right = mid - 1
    if right < 0 or nums[right] != target:
        return -1
    return right


nums = [1, 8, 9, 7, 4, 5, 3, 1, 6]
target = 6
result = left_Search(nums, target)
print(result)  # 8
# 6所在的索引位置正是 8
  • 此处要注意的是:
  • 主要是要理解右边界查找和左边界查找的区别,在左边界查找时nums[mid] == target我们要去查找左边的区间是否有指定数,所以当nums[mid] == target时我们要将右边界设置为mid - 1,再次进行循环
  • 而在右查找时我们要去查找右边的区间是否有指定数,所以当nums[mid] == target时我们要将左边界设置为mid - 1

【二】冒泡排序

【1】介绍

  • 两个数比较大小,较大的数下沉,较小的数冒起来

【2】排序过程

  • 比较相邻的两个数据,如果第二个数小,就交换位置
  • 从后向前两两比较,一直到比较最前两个数据
  • 最终最小数被交换到起始的位置,这样第一个最小数的位置就排好了
  • 继续重复上述过程,依次将第2.3...n-1个最小数排好位置
def bubble_sort(data):
    for i in range(len(data)):
        print(f'这是后{i}趟')
        for j in range(len(data) - 1 - i):
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]
        print('差的排序结果为:>>>', data)


start_list = [3, 9, 3, 1, 8, 7]
bubble_sort(start_list)
# 这是后0趟
# 差的排序结果为:>>> [3, 3, 1, 8, 7, 9]
# 这是后1趟
# 差的排序结果为:>>> [3, 1, 3, 7, 8, 9]
# 这是后2趟
# 差的排序结果为:>>> [1, 3, 3, 7, 8, 9]
# 这是后3趟
# 差的排序结果为:>>> [1, 3, 3, 7, 8, 9]
# 这是后4趟
# 差的排序结果为:>>> [1, 3, 3, 7, 8, 9]
# 这是后5趟
# 差的排序结果为:>>> [1, 3, 3, 7, 8, 9]

标签:target,nums,Python,高级,mid,算法,查找,data,left
From: https://www.cnblogs.com/ligo6/p/18179993

相关文章

  • Python高级之常用的内置函数
    【一】什么是内置函数内置函数就是Python给你提供的,拿来直接用的函数目前共有68个内置函数Built-inFunctionsAabs()aiter()all()any()anext()ascii()Bbin()bool()breakpoint()bytearray()bytes()Ccallable()chr()classmethod()compile()complex()Ddelatt......
  • Python高级之模块与包
    【一】模块介绍【1】什么是模块在Python中,一个py文件就是一个模块,文件名为xxx.py模块名则是xxx,导入模块可以引用模块中已经写好的功能使用模块既保证了代码的重用性,又增强了程序的结构性和可维护性另外除了自定义模块外,我们还可以导入使用内置或第三方模块提供的现成功能......
  • 《最新出炉》系列入门篇-Python+Playwright自动化测试-45-鼠标操作-下篇
    1.简介鼠标为我们使用电脑提供了很多方便,我们看到的东西就可以将鼠标移动过去进行点击就可以打开或者访问内容,当页面内容过长时,我们也可以使用鼠标滚轮来实现对整个页面内容的查看,其实playwright也有鼠标操作的方法。上一篇文章中已经讲解过鼠标的部分操作了,今天宏哥在这里将剩下......
  • Python高级之函数参数进阶Optional
    【一】引言在Python3.5版本后引入的typing模块为Python的静态类型注解提供了支持。这个模块在增强代码可读性和维护性方面提供了帮助。本文将深入探讨typing模块,介绍其基本概念、常用类型注解以及使用示例,以帮助读者更全面地了解和应用静态类型注解。【二】基本类型注解【......
  • Python高级之名称空间和作用域
    【一】名称空间【1】什么是名称空间名称空间就是存放函数名与函数值对应关系的地方内存空间就是申请一块内存空间,然后将函数值放到内存空间里再将变量名和变量值绑定存到名称空间里程序执行期间最多会存在三种名称空间【2】内置名称空间会跟着python解释器的启动而生成,......
  • Python高级之匿名函数
    【一】匿名函数的定义在Python里有两类函数:用def关键词定义的正规函数用lambda关键词定义的匿名函数lambda参数:表达式lambda:定义匿名函数的关键词。函数参数它们可以是位置参数、默认参数、关键字参数表达式,输入函数参数,输出一些值,表达式本身结果就是返回......
  • Python高级之函数对象与闭包函数
    【一】函数对象函数对象是指函数可以被当成数据来处理,python中一切皆为对象【1】函数可以被引用defadd(a,b):returna+bres=add(3,4)print(res)#7【2】函数作为容器类型的元素defadd(a,b):returna+bnum_list=[add,1]res=num_list[0......
  • 国密算法SM3-java实现
    maven依赖<dependency><groupId>org.bouncycastle</groupId><artifactId>bcprov-jdk15on</artifactId><version>1.56</version></dependency> SM3Utilsimportorg.bouncycastle.crypto.digests.SM3Dig......
  • Python高级之函数的参数
    【一】形参和实参函数的参数分为形参和实参,形参就是定义在函数名后面括号里的参数(用来接收外部传来的值),实参就是调用函数时,括号里传进去的值(值可以是常量、变量、表达式)defadd(x,y):returnx+y#实参是常量print(add(3,4))#输出7#实参是变量x=3y=4prin......
  • Python高级之函数
    【一】函数的基本使用我们在前面的学习中,所有的功能代码都集中在一块,需要使用同一功能时,需重复编写该功能的代码,这样比较麻烦,当我们到后面代码变得越来越长,也不利于我们修改其中一个小功能的代码我们完全可以从现实生活中找到简化程序设计的方案:比如一个修理工会事先准备好螺......