专栏首页软件测试小助手python算法题练习---二分法

python算法题练习---二分法

导言:记录下学习的算法题,写练多,脑子才能转的快!

今日算法题:二分法查找

说下我对于二分法查找的理解:【和猜数字游戏差不多】

要在一个有序数列中找到一个与对应给定数字。

1、找到有序数列中最中间的数字

2、若中间值大于给定值,则在左边数列重新二分查找

3、若中间值小于给定值,则在右边数列重新二分查找

4、若都不存在,则返回‘没有对应的匹配值’

【索引思想】

1、设置最大和最小索引,找到中间索引值

2、若中间索引值大于给定值,则中间索引位置前一位变为最大索引位置,最小索引位为0;

3、若中间索引值小于给定值,则中间索引位置下一位变为最小索引位置,最大索引位不变;

4、若都不存在,则返回‘没有对应的匹配值’

错误的代码,没有考虑数组的改变会导致索引的位置变化

if len(arr) >= 1:
    mid = int((len(arr)-1)/2)
    if arr[mid] == number:
        return mid
    elif arr[mid] < number:
        return searchBinary(arr[mid+1::], number)
    elif arr[mid] > number:
        return searchBinary(arr[::mid-1], number)
else:
    print('没有匹配的值')

于是,我考虑了索引位置的改变

def searchBinary(arr, number):
    low = 0
    height = len(arr)-1
    while low <= height:
        mid = int((low+height)/2)
        if arr[mid] > number:
            height = mid-1
        elif arr[mid] < number:
            low = mid+1
        else:
            return mid
    return '没有匹配值'

但是又想要用递归来实现

def searchBinary(arr, number,low,height):
    if low <= height:
        mid = int((low+height)/2)
        if arr[mid] == number:
            return mid
        elif arr[mid] >= number:
            return searchBinary(arr, number, 0, mid-1)
        else:
            return searchBinary(arr, number, mid+1, height)
    else:
        return '没有匹配'

本文分享自微信公众号 - 软件测试小助手(gh_2282fef3410c),作者:小雯子打豆豆

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python练习题(二)

    # 1.字符串最后一个单词的长度 题目描述:计算字符串最后一个单词的长度,单词以空格隔开。 输入描述: 一行字符串,非空,长度小于5000。 输出描述:...

    py3study
  • 算法学习笔记-二分法

    leetcode875爱吃香蕉的珂珂https://leetcode-cn.com/problems/koko-eating-bananas/

    买唯送忧
  • 算法-二分查找算法(OC、Swift、Python)

    二分查找在程序开发过程中是十分常见的算法,也是在程序员面试过程中关于算法的知识点考察过程中最常问的知识点;二分查找在实际开发过程中也常常用的到;就比如在一个一维...

    用户6004386
  • 《算法图解》第一章笔记与课后练习_二分查找算法

    Zoctopus
  • 二分查找算法(Python)

    二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。

    流柯
  • Python算法 二分查找

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 每周算法练习——大数的乘法问题

        大数问题的思路是使用矩阵或者字符串来存储,今天我试着用Java实现了这样的功能,这段程序只是基本模拟大数乘法,当然实现的只是基本的原理。 Java代码:...

    zhaozhiyong
  • 每周算法练习——大数的乘法问题

        大数问题的思路是使用矩阵或者字符串来存储,今天我试着用Java实现了这样的功能,这段程序只是基本模拟大数乘法,当然实现的只是基本的原理。

    zhaozhiyong
  • python有序查找算法:二分法

    二分法是一种快速查找的方法,时间复杂度低,逻辑简单易懂,总的来说就是不断的除以2除以2...

    机器学习和大数据挖掘
  • 程序员进阶之算法练习(二十二)

    前言 时间来到6月,又是一年高考时。 几年之前是坐在教室怀念高考,现在是上班敲着代码怀念学生时代。 正文 1、Lakes in Berland 题目链接 ...

    落影
  • 程序员进阶之算法练习(二)

    前言 看完题目大意,先思考,再看解析;觉得题目大意不清晰,点击题目链接看原文。 A 题目链接 题目大意:n个点,坐标x[i]从小到大,每个点可以选择Le...

    落影
  • 算法学习|二分查找

    微笑的小小刀
  • 每周算法练习——n皇后问题

    一、八皇后问题的描述     八皇后问题是一个以国际象棋为背景的问题:如何能够在8×8的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为...

    zhaozhiyong
  • 每周算法练习——最近对问题

    一、最近对问题的解释     看到算法书上有最近对的问题,简单来讲最近对问题要求出一个包含 ? 个点的集合中距离最近的两个点。抽象出来就是求解任意两个点之间的距...

    zhaozhiyong
  • 每周算法练习——n皇后问题

        八皇后问题是一个以国际象棋为背景的问题:如何能够在8×8的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇...

    zhaozhiyong
  • 每周算法练习——最近对问题

    个点的集合中距离最近的两个点。抽象出来就是求解任意两个点之间的距离,返回距离最小的点的坐标,以及最小距离。这里会使用到欧式距离的求法:

    zhaozhiyong
  • 五分钟学算法之经典算法题:二分查找

    今天分享一道简单的笔试题,题目来源于京东校园招聘笔试真题。你做出这道简单的题目需要花费多少东分钟呢?

    五分钟学算法
  • 算法——二分查找算法

    介绍:二分查找,也称折半搜索,是一种在 有序数组 中 查找某一特定元素 的搜索算法。下面简单介绍其优缺点,以及编码实现。

    凡人飞
  • 程序员进阶之算法练习(十二)

    前言 题目地址在HDU,输入对应的题号即可看到题目,在百度搜索hdu+对应的题号可以看到题解。 我简单的对题目难度进行了划分: 简单题:想法题,实现简单...

    落影

扫码关注云+社区

领取腾讯云代金券