精华内容
下载资源
问答
  • python折半查找 使用递归的方式实现折半查找
    千次阅读
    2018-10-13 15:56:08

    python经典算法之折半查找

    1、折半查找

    def s2(li,key):
        li.sort()
        start=0
        end=len(li)-1
        while start<end:
            mid=(start+end)//2
            if li[mid]==key:
                return mid
            elif li[mid]<key:# 后半段
                start=mid+1
            else:
                end=mid-1
        return -1
    li=[1,44,55,8,6,-5]
    print(sorted(li))#[-5, 1, 6, 8, 44, 55]
    print(s2(li,44))#4

    2、使用递归的方式实现折半查找

    li=[23,-8,26,-2,-6,-18,33]
    li.sort()
    # print(li)
    n=len(li)
    def fun(li,key,start,end):
        if li[0]<=key<=li[-1]:
            mid = (start+end)//2
            if li[mid]==key:
                return mid
            if start>end:
                return "查不到"
            elif li[mid]<key:
                return fun(li,key,mid+1,end)
            else:
                return fun(li,key,start,mid-1)
        else:
            return "查不到"
    # print(fun(li,23,0,n-1))#4
    # print(fun(li,3,0,n-1))#查不到
    # print(fun(li,-100,0,n-1))#查不到

     

    更多相关内容
  • 主要介绍了python实现折半查找和归并排序算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • Python折半查找(二分查找)

    千次阅读 2020-04-30 10:04:39
    本题要求采用折半查找的思想,每次搜索原来数据的一半,直到搜索成功或待搜索数据为空。 1.1 输入格式 输入一个列表A和查找的值B。 1.2 输出格式 如果查找成功输出数B在列表A中的位置,否则输出查找不成功。 1.3 输....


    1. 题目🔍

    本题要求采用折半查找的思想,每次搜索原来数据的一半,直到搜索成功或待搜索数据为空。

    1.1 输入格式

    输入一个列表A和查找的值B。

    1.2 输出格式

    如果查找成功输出数B在列表A中的位置,否则输出查找不成功。

    1.3 输入样例1

    [19,23,46,49,65,78,98,101,125]
    46

    1.4 输出样例1

    46 2

    1.5 输入样例2

    [19,23,46,49,65,78,98,101,125]
    82

    1.6 输出样例2

    not find


    2. 题解✨

    2.1 思路

    使用eval()将输入的值转化为列表,使用sorted()将列表排序

    关键 创建一个折半查找的函数,传入值为列表A与数字B

    折半查找判断方法:

    将列表中间位置的值与查找值比较

    • 如果两者相等,则查找成功;否则,利用中间位置的值将表分成前、后两个子列表,
    • 如果中间位置记录的值大于查找值,则进一步查找一子列表;
    • 如果中间位置记录的值小于查找值,则进一步查找一子列表。

    重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

    2.2 代码

    a = sorted(eval(input()))		# 将输入转化为列表,并排序
    b = int(input())
    
    
    def find(ls, item):
        low = 0
        high = len(ls)
        while low < high:
            mid = int((low + high)/2)
            temp = ls[mid]
            if temp == item:
                return mid
            elif temp > item:
                high = mid - 1
            else:
                low = mid + 1
        return False
    
    
    if find(a, b) is False:
        print('not find')
    else:
        print('{} {}'.format(b, find(a, b)))
    
    

    相关内容

    展开全文
  • Python折半查找

    2021-05-13 18:57:50
    折半查找 “”" 0 1 2 3 4 5 6 7 8 9 list = [11,22,33,44,55,66,77,88,99,111] 假设需要:66 第一次:(0+9)//2 = 4 ;55和66比较 接下来55的右边找:66,77,88,99,111 第二次:(5+9)//2 = 7 ; 88和66比较 接...

    折半查找

    “”"
    0 1 2 3 4 5 6 7 8 9
    list = [11,22,33,44,55,66,77,88,99,111]
    假设需要:66
    第一次:(0+9)//2 = 4 ;55和66比较
    接下来55的右边找:66,77,88,99,111
    第二次:(5+9)//2 = 7 ; 88和66比较
    接下来在88左边找,66,77
    第三个:(5+6)//2 = 5 ; 66==66,下标对应5
    开始下标:0开始,慢慢变大 5 6
    结尾下标:(个数 - 1) 慢慢减小 6 5

    “”"

    list = [11,22,33,44,55,66,77,88,99,110]
    n = int(input("输入需要查找的值:"))
    start = 0 #最左边开始下标
    end = len(list)-1 #最右边开始的下标
    index = -1 #对应的下标 -1没有找到
    while start <= end :
        #中间值与n进行比较
        mid = (start+end)//2
        if list[mid] == n: #数值被找到
            index = mid
            break
        elif list[mid] < n: ##继续 在中间值的右边查找
            start = mid + 1
        else:
            end = mid -1
    print("%d 对应下标:%d"%(n,index))
    
    展开全文
  • # -*- coding:utf8 -*- def bin_search(items, key): '''折半查找''' start, end = 0, len(items) - 1 while start <= end: mid = (start + end) // 2 if key > items[mid]: ...
    # -*- coding:utf8 -*-
    def bin_search(items, key):
        '''折半查找'''
        start, end = 0, len(items) - 1
        while start <= end:
            mid = (start + end) // 2
            if key > items[mid]:
                start = mid + 1
            elif key < items[mid]:
                end = mid - 1
            else:
                return mid
    
        return -1
    
    print(bin_search([3.2,2,10,3,1,45,90,0], 3))
    
    展开全文
  • python折半查找算法

    千次阅读 2019-06-01 16:53:06
    折半查找算法也叫二分查找算法。这里必须基于查找的数据是有序的,然后该算法是没有意义的。我觉得代码比较直观,所以我就直接给出代码了。 折半查找非递归算法 #折半查找非递归算法 #折半查找函数 #参数 数组 起始...
  • python算法1.9折半查找

    2022-02-28 14:18:03
    折半查找 1.问题描述 N个有序整数数列已放在一维数组中,利用二分查找法查找整数m在数组中的位置。若找到,则输出其下标值;反之,则输出“Not be found!”。 2.解决方案 二分查找法(也叫折半查找)其本质是分治...
  • 0 1 2 3 4 5 6 7 8 9 list = [11,22,33,44,55,66,77,88,99,111] 假设需要:66 第一次:(0 + 9)//2 = 4 ;55 和66比较, 接下来在55的右边找:66,77,88,99,111 第二次:(5+9)//2 = 7 88和66 ...
  • 折半查找又叫二分查找,要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列(升序或者降序)。 时间复杂度:O(log2n) 每次循环都会舍弃一半的查找空间。 空间复杂度:O(1) 使用一个整型变量mid记录中间...
  • 折半查找python实现

    千次阅读 2019-05-01 10:45:34
    折半查找python实现 折半查找是常用的查找方法(在按大小顺序排列中的数组或者列表中更是如此),与传统的顺序查找相比,它查找的效率更高。 算法思想 算法的思想很直接,也就是先把第一个和最后一个作为作为low和...
  • 二分查找又称折半查找 优点是比较次数少,查找速度快,平均性能好; 缺点是要求待查表为有序表,且插入删除困难。 因此,折半查找方法适用于不经常变动而查找频繁的有序列表。 ####################非递归方法#...
  • python 二分查找算法函数bi_search(),该函数实现检回忆,很美却很伤;回忆只是回不到过去的记忆。输入格式: 第一行为正整数 n 接下来若干行为待查找的数字,每行输入一个总是女人为了天长地久而烦恼,男人却可以洒脱...
  • 介绍二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。前提必须待查找的序列有序时间复杂度O(log2n)原理1)确定该...
  • Python实现二分查找法(基于顺序表)class List:elem=[] #存储顺序表元素last=-1 #设置初始为-1SeqList = List() #创建一个顺序表print("欢迎来到我的二分查找(停止输入……Y,继续输入……N),回车开始下一次输入")...
  • python php 折半查找

    2019-09-30 13:42:44
    二分查找 python实现 #!/usr/bin/python # 输入的列表必须是已经排好序的列表 def binary_search(li, val): left = 0 #定义开始范围 right = len(li)-1 #定义查找结束范围 while left <= right: #如果左边...
  • 折半查找要求序列已经是有序的。 def binsearch(a,k): ## 对于已经排好序的序列 alen = len(a) low = 0 hi = alen - 1 while low <= hi: mid = (low + hi) // 2 if a[mid] == k: return mid elif a[mid...
  • Python 折半查找

    2020-12-06 11:02:38
    '''二分查找也称折半查找(BinarySearch),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排'''importrandomdef BinarySearch(findlist,target):'''findlist:...
  • Python实现二分查找(折半查找)

    千次阅读 2019-10-06 19:06:37
    我们在学习编程语言或者算法设计的时候,总是绕不过查找算法和排序算法。对于顺序查找和冒泡查找我们应该是最熟悉的了,如果这两个还不会,真的要加把劲儿了。刚好最近算法老师在讲分治思想,刚好二分...
  • 折半查找 python

    2020-04-16 15:10:36
    # 折半查找 在一个基本有序的数列中查找一个数字 def search(a,list): n=len(list) left=0 right=n-1 mid=(left+right)//2 while(left<=right): if(a>list[mid]): right=mid-1 e...
  • /usr/bin/env python # -*- coding:utf-8 -*- # 算法基础:二分查找/折半查找 def binarySearch(dataSource, find_n): mid = int(len(dataSource) / 2) if len(dataSource) >= 1: if dataSource[mid] > find_n: print...
  • importtimedefcal_time(func):defwrapper(*args,**kwargs):start_time=time.time()res=func(*args)end_time=time.time()print('runningtimeis{}'.format(end_time-start_time))returnresreturnwrapper...
  • 二分查找(名折半查找)的查找过程:先确定待查找记录所在的范围(区间),然后逐步缩小范围直到 找到或 找不到 该记录为止。 二分经常让手写,注意边界。 时间复杂度为 :O(log2n),log以2为底 n 的对数,可以简...
  • python--search--折半查找

    2019-10-25 19:51:50
    方法一:使用折半查找 def insert_sort(a, c): high_position = len(a) - 1 low_position = 0 if a: while low_position <= high_position: middle_position = int((high_position + low_...
  • 请设计一个程序, 使用折半查找算法通过最少次数的比较找到指定学号的学生, 如果有, 输出这个学生的学号和姓名, 如果没有, 输出报告未找到该学生。 列表中存储数据为stu_list= [['201801','zhangyi'],['201802',...
  • = key: i -= 1 if i > -1: return i else: return -1 def bin_search(record_list: RecodeList, key): """ 折半查找法 对待查列表的要求: (1) 必须采用顺序存储结构 (2) 必须按关键字大小有序排列 算法思想: 首先...
  • python实现顺序查找和折半查找

    千次阅读 2017-07-01 19:29:20
    1 顺序查找 特点:不需要内容有序,一个一个查找 缺点:查找效率低,不适合大数据 ,假设数据的总个数为n,则计算复杂度为n/2 下面的程序由三个函数组成,第一个函数是装饰器,作用是计算函数的 运行时间  第二个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,041
精华内容 1,216
关键字:

python折半查找

友情链接: day4.zip