Python算法练习之二分查找算法的实现

目录
  • 1. 算法描述
  • 2. 算法分析
  • 3. 算法思路
  • 4. 代码实现
    • 纯算法实现
    • 递归法实现

1. 算法描述

二分法是一种效率比较高的搜索方法

回忆之前做过的猜数字的小游戏,预先给定一个小于100的正整数x,让你猜猜测过程中给予大小判断的提示,问你怎样快速地猜出来?

我们之前做的游戏给定的是10次机会,如果我们学会.二分查找法以后,不管数字是多少,最多只需要7次就能猜到数字。

2. 算法分析

1、必须是有序的序列。

2、对数据量大小有要求。

数据量太小不适合二分查找,与直接遍历相比效率提升不明显。

数据量太大也不适合用二分查找,因为数组需要连续的存储空间,若数据量太大,往往找不到存储如此大规模数据的连续内存空间。.

3. 算法思路

假设有一个有序列表如下:

请问数字11是否在此列表中,如果在它的索引值为多少?

4. 代码实现

纯算法实现

实现代码

arr_list = [5, 7, 11, 22, 27, 33, 39, 52, 58]
# 需要查找的数字
seek_number = 11
# 保存一共查找了几次
count = 0
# 列表左侧索引
left = 0
# 列表右侧索引
right = len(arr_list) - 1
# 当左侧索引小于等于右侧索引时
while left <= right:
    # 取中间的索引位置
    middle = (left + right) // 2
    # 查找次数进行累加
    count += 1
    # 如果查找的数字大于中间位置的数字时
    if seek_number > arr_list[middle]:
        # 左侧索引为中间位置索引+1
        left = middle + 1
    # 如果查找的数字小于中间位置的数字时
    elif seek_number < arr_list[middle]:
        # 右侧索引为中间位置索引-1
        right = middle - 1
    # 如果等于中间索引数据
    else:
        print('数字:%s找到了,索引值为:%s' % (seek_number, middle))
        break
else:
    print("数字%s 没有找到" % seek_number)
print("一共用了:%s次查找" % count)

运行结果

递归法实现

在循环中定义了一个变量count,如果第一次循环后count没有变化,就说明输入的是有序序列,这时我们直接return退出循环,这时候的时间复杂度为O(n)

实现代码

arr_list = [5, 7, 11, 22, 27, 33, 39, 52, 58]

def binary_search(seek_number, left, right):
    if left <= right:
        middle = (left + right) // 2
        if seek_number < arr_list[middle]:
            right = middle - 1
        elif seek_number > arr_list[middle]:
            left = middle + 1
        else:
            return middle
        # 进行递归调用
        return binary_search(seek_number, left, right)
    # 当左侧索引大于右侧索引时,说明没有找到
    else:
        return -1

# 查找的数字
seek_number = 11
# 列表左侧索引
left = 0
# 列表右侧索引
right = len(arr_list) - 1
print("查找的数字:%s,索引为:%s" % (seek_number, binary_search(seek_number, left, right)))

运行结果

以上就是Python算法练习之二分查找算法的实现的详细内容,更多关于Python二分查找算法的资料请关注我们其它相关文章!

(0)

相关推荐

  • python二分查找算法的递归实现方法

    本文实例讲述了python二分查找算法的递归实现方法.分享给大家供大家参考,具体如下: 这里先提供一段二分查找的代码: def binarySearch(alist, item): first = 0 last = len(alist)-1 found = False while first<=last and not found: midpoint = (first + last)//2 if alist[midpoint] == item: found = True else: if ite

  • python实现二分查找算法

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

  • Python实现二分查找算法实例

    本文实例讲述了Python实现二分查找算法的方法.分享给大家供大家参考.具体实现方法如下: #!/usr/bin/env python import sys def search2(a,m): low = 0 high = len(a) - 1 while(low <= high): mid = (low + high)/2 midval = a[mid] if midval < m: low = mid + 1 elif midval > m: high = mid - 1 else:

  • Python如何实现的二分查找算法

    先来看个用Python实现的二分查找算法实例 import sys def search2(a,m): low = 0 high = len(a) - 1 while(low <= high): mid = (low + high)/2 midval = a[mid] if midval < m: low = mid + 1 elif midval > m: high = mid - 1 else: print mid return mid print -1 return -1 if _

  • Python算法练习之二分查找算法的实现

    目录 1. 算法描述 2. 算法分析 3. 算法思路 4. 代码实现 纯算法实现 递归法实现 1. 算法描述 二分法是一种效率比较高的搜索方法 回忆之前做过的猜数字的小游戏,预先给定一个小于100的正整数x,让你猜猜测过程中给予大小判断的提示,问你怎样快速地猜出来? 我们之前做的游戏给定的是10次机会,如果我们学会.二分查找法以后,不管数字是多少,最多只需要7次就能猜到数字. 2. 算法分析 1.必须是有序的序列. 2.对数据量大小有要求. 数据量太小不适合二分查找,与直接遍历相比效率提升不明显

  • PHP二分查找算法的实现方法示例

    本文实例讲述了PHP二分查找算法的实现方法.分享给大家供大家参考,具体如下: 二分查找法需要数组是一个有序的数组 假设我们的数组是一个递增的数组,首先我们需要找到数组的中间位置. 1. 要知道中间位置就需要知道起始位置和结束位置,然后取出中间位置的值来和我们的值做对比. 2. 如果中间值大于我们的给定值,说明我们的值在中间位置之前,此时需要再次二分,因为在中间之前,所以我们需要变的值是结束位置的值,此时结束位置的值应该是我们此时的中间位置. 3. 反之,如果中间值小于我们给定的值,那么说明给定值

  • Java 二分查找算法的实现

    二分查找又称折半查找,它是一种效率较高的查找方法. 折半查找的算法思想是将数列按有序化(递增或递减)排列,查找过程中采用跳跃式方式查找,即先以有序数列的中点位置为比较对象,如果要找的元素值小 于该中点元素,则将待查序列缩小为左半部分,否则为右半部分.通过一次比较,将查找区间缩小一半. 折半查找是一种高效的查找方法.它可以明显减少比较次数,提高查找效率.但是,折半查找的先决条件是查找表中的数据元素必须有序. 折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删

  • Python查找算法之折半查找算法的实现

    一.折半查找算法 折半查找算法又称为二分查找算法,折半查找算法是将数据分割成两等份,首先用键值(要查找的数据)与中间值进行比较.如果键值小于中间值,可确定要查找的键值在前半段:如果键值大于中间值,可确定要查找的键值在后半段.然后对前半段(后半段)进行分割,将其分成两等份,再对比键值.如此循环比较.分割,直到找到数据或者确定数据不存在为止.折半查找的缺点是只适用于已经初步排序好的数列:优点是查找速度快. 生活中也有类似于折半查找的例子,例如,猜数字游戏.在游戏开始之前,首先会给出一定的数字范围(例

  • Python查找算法之分块查找算法的实现

    一.分块查找算法 分块查找是二分法查找和顺序查找的改进方法,分块查找要求索引表是有序的,对块内结点没有排序要求,块内结点可以是有序的也可以是无序的. 分块查找就是把一个大的线性表分解成若干块,每块中的节点可以任意存放,但块与块之间必须排序.与此同时,还要建立一个索引表,把每块中的最大值作为索引表的索引值,此索引表需要按块的顺序存放到一个辅助数组中.查找时,首先在索引表中进行查找,确定要找的结点所在的块.由于索引表是排序的,因此,对索引表的查找可以采用顺序查找或二分查找:然后,在相应的块中采用顺序

  • 详解Python查找算法的实现(线性、二分、分块、插值)

    目录 1. 线性查找 2. 二分查找 3. 插值查找 4. 分块查找 5. 总结 查找算法是用来检索序列数据(群体)中是否存在给定的数据(关键字),常用查找算法有: 线性查找:线性查找也称为顺序查找,用于在无序数列中查找. 二分查找:二分查找也称为折半查找,其算法用于有序数列. 插值查找:插值查找是对二分查找算法的改进. 分块查找:又称为索引顺序查找,它是线性查找的改进版本. 树表查找:树表查找又可分二叉查找树.平衡二叉树查找. 哈希查找:哈希查找可以直接通过关键字查找到所需要数据. 因树表查找

  • Python查找算法之插补查找算法的实现

    一.插补查找算法 插补查找算法又称为插值查找,它是折半查找算法的改进版.插补查找是按照数据的分布,利用公式预测键值所在的位置,快速缩小键值所在序列的范围,慢慢逼近,直到查找到数据为止.根据描述来看,插值查找类似于平常查英文字典的方法.例如,在查一个以字母 D 开头的英文单词时,决不会用折半查找法.根据英文词典的查找顺序可知,D 开头的单词应该在字典较前的部分,因此可以从字典前部的某处开始查找.键值的索引计算,公式如下: middle=left+(target-data[left])/(data[

  • Python机器学习实战之k-近邻算法的实现

    目录 K-近邻算法概述 工作原理 实施KNN算法 示例:手写识别系统 K-近邻算法概述 简单地说, k-近邻算法采用测量不同特征值之间的距离方法进行分类. k-近邻算法 优点:精度高.对异常值不敏感.无数据输入假定. 缺点: 计算复杂度高.空间复杂度高. 适用数据范围: 数值型和标称型. 工作原理 存在一个样本数据集合, 也称作训练样本集, 并且样本集中每个数据都存在标签, 知道样本集中每一数据与所属分类的对应关系. 输入没有标签的新数据后, 将新数据的每个特征与样本集中数据对应的特征进行比较,

  • JavaScript数据结构与算法之检索算法示例【二分查找法、计算重复次数】

    本文实例讲述了JavaScript数据结构与算法之检索算法.分享给大家供大家参考,具体如下: javascript数据结构与算法---检索算法(二分查找法.计算重复次数) /*只需要查找元素是否存在数组,可以先将数组排序,再使用二分查找法*/ function qSort(arr){ if (arr.length == 0) { return []; } var left = [];//存储小于基准值 var right = [];//存储大于基准值 var pivot = arr[0]; fo

随机推荐