美文网首页算法
算法入门——顺序查找、二分查找

算法入门——顺序查找、二分查找

作者: 白巧克力LIN | 来源:发表于2022-08-18 16:02 被阅读0次

顺序查找

顺序查找也叫线性查找,从列表第一个元素开始,顺序进行搜索,直到找到元素或搜索到列表最后一个元素为止。

例如1~100的数字,如果我们想要的数字为100,那么程序需要查找100次才能找到。所以顺序查找称为傻找。

顺序查找代码逻辑:通过for循环遍历列表的值和下标,再将值与你想查找的值作比较,两值相等就返回该值的下标即可。

示例代码如下:

li=[1,2,5,3,'十',6,8,9]
def linear_search(li,value):
    for i,v in enumerate(li):       # 遍历li列表的值和下标
        if v==value:
            return i
print(linear_search(li,8))

这里使用enumerate方法获取列表元素的值和下标。

顺序查找的时间复杂度为:O(n)。

二分查找

二分查找是从有序列表的中间位置开始查找,每次查找后进行判断满足要求的元素在左边还是在右边。

例如:我们从1~15的数字中查找6这个数字,使用二分查找查找如下图所示:

如上图所示:使用二分查找时,每次都能排除一半的数字,这样我们只需要查找3次就可以找到满足查找要求的元素。

二分查找的实现关键在于:区分好满足条件的元素左右区域。

示例代码如下:

def binary_search(li, val):
    left = 0
    right = len(li) - 1
    while left <= right:     # 候选区有值
        mid = (left + right) // 2
        if li[mid] == val:
            return f'查找元素的下标为:{mid}'
        elif li[mid] > val:  # 待查找的值在中间位置的左侧
            right = mid - 1
            print('满足条件的列表元素有:',li[left:right+1])
        else:                # 待查找的值在中间位置的右侧
            left=mid +1
            print('满足条件的列表元素有:',li[left:right+1])
    else:
        return '你查找的元素不在列表中'
print(binary_search([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15],6))

运行结果如下:

这样就成功获取到了6这个元素的下标5了。

二分查找的时间复杂度为:O(logn)。

好了,关于算法入门——顺序查找、二分查找就学到这里,下篇文章我们学习算法入门——冒泡排序、选择排序。

相关文章

  • 算法

    一.算法基础--算法的特性 二.算法基础--算法的复杂度 三.顺序查找和二分查找 顺序查找 二分查找(前提是有序的...

  • 算法入门——冒泡排序、选择排序

    上篇文章学习了算法入门——顺序查找、二分查找,这篇文章我们学习算法入门——冒泡排序、选择排序。 冒泡排序 冒泡排序...

  • 排序查找c++

    排序算法 选择排序 顺序查找 二分查找

  • 二分查找算法

    一、二分查找算法 二分查找算法又称为折半查找算法,它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序...

  • PHP经典算法题

    PHP学习之路---算法题 1.使用PHP描述顺序查找和二分查找(也叫做折半查找)算法,顺序查找必须考虑效率,对象...

  • day13

    查找算法 顺序查找 二分查找 差值查找 斐波那契查找 二分查找 前提数组必须是有序的。 升级 Interpolat...

  • 查找算法

    三种查找算法:顺序查找,二分法查找(折半查找),分块查找,散列表

  • 基本算法

    冒泡算法 选择排序 插入排序 顺序查找 二分查找

  • 查找算法

    查找算法 1顺序查找 2二分查找 2.1二分查找思路分析 2.2代码实现 3插值查找 3.1插值查找原理介绍: ​...

  • PHP算法

    PHP算法 使用PHP描述顺序查找和二分查找(也叫做折半查找)算法,顺序查找必须考虑效率,对象可以是一个有序数组二...

网友评论

    本文标题:算法入门——顺序查找、二分查找

    本文链接:https://www.haomeiwen.com/subject/nuvegrtx.html