python实现二分查找算法-阿里云开发者社区

开发者社区> python之战> 正文

python实现二分查找算法

简介: 二分查找算法,是常见的搜索算法之一,适用于有序的序列,通过将序列不断的对折分为区间,从而确定查找值是否存在,优点是速度快。 首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。
+关注继续查看

二分查找算法,是常见的搜索算法之一,适用于有序的序列,通过将序列不断的对折分为区间,从而确定查找值是否存在,优点是速度快。

首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

使用python递归实现其算法:

def binary_search(items: list, item: str) -> float:

    if not len(items):
        return False
    if item > items[-1]:
        return False
    elif item < items[0]:
        return False
    n = len(items) // 2
    if items[n] == item:
        return True
    else:
        if items[n] < item:
            return binary_search(items[n:], item)
        else:
            return binary_search(items[:n], item)


二分查找是应用在数据量较大的场景中,如一些图片的RGB数组操作中,典型的是在滑块验证中使用二分法来确定最佳距离。

   def match(self, target, template):
        img_rgb = cv2.imread(target)
        img_gray = cv2.cvtColor(img_rgb, cv2.COLOR_BGR2GRAY)
        template = cv2.imread(template,0)
        run = 1
        w, h = template.shape[::-1]
        print(w, h)
        res = cv2.matchTemplate(img_gray,template,cv2.TM_CCOEFF_NORMED) 

        # 使用二分法查找阈值的精确值 
        L = 0
        R = 1
        while run < 20:
            run += 1
            threshold = (R + L) / 2
            print(threshold)
            if threshold < 0:
                print('Error')
                return None
            loc = np.where( res >= threshold)
            print(len(loc[1]))
            if len(loc[1]) > 1:
                L += (R - L) / 2
            elif len(loc[1]) == 1:
                print('目标区域起点x坐标为:%d' % loc[1][0])
                break
            elif len(loc[1]) < 1:
                R -= (R - L) / 2

        for pt in zip(*loc[::-1]):
            cv2.rectangle(img_rgb, pt, (pt[0] + w, pt[1] + h), (7279151), 2)
        cv2.imshow('Dectected', img_rgb)
        cv2.waitKey(0)
        cv2.destroyAllWindows()
        return loc[1][0]


2019-04-21-23_34_01.png

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
python实现选择排序算法
选择排序,简单而直观,其原理是把序列中的最小值或者最大值找出来放在起始位置,然后再从剩下的序列中找出极值放到起始位置之后,以此类推最后就完成排序。 完成这个过程大致思想:首先需要一个记录器,记录排序排到第几个位置了,然后在剩余的序列中找到极值下标,最后将记录器位置和极值位置元素交换,完成本次选择排序。
1207 0
python实现插入排序算法
插入排序,其原理是通过构建一个初始的有序序列,然后从无需序列中抽取元素,插入到有序序列的相对排序位置,就像将一堆编号混乱的书,一本一本的放到书架上,找到上下编号之间的位置插入,最后完成整理。 python实现插入排序并不难,从第二个位置开始遍历,与它前面的元素相比较,如果比前面元素小就交换位置,实...
838 0
【大创_社区划分】——PageRank算法的解析与Python实现
一、什么是pagerank PageRank的Page可是认为是网页,表示网页排名,也可以认为是Larry Page(google 产品经理),因为他是这个算法的发明者之一,还是google CEO(^_^)。
1110 0
InnoDB索引概述,二分查找法,平衡二叉树
索引是应用程序设计和开发的一个重要方面。如果索引太多,应用的性能可能会受到影响;如果索引太少,对查询性能又会产生影响。要找到一个合适的平衡点,这对应用的性能至关重要。 如果知道数据的使用,从一开始就应该在需要处添加索引。
1061 0
人工智能: 自动寻路算法实现(二、深度优先搜索)
前言 本篇文章是机器人自动寻路算法实现的第二章。我们要讨论的是一个在一个M×N的格子的房间中,有若干格子里有灰尘,有若干格子里有障碍物,而我们的扫地机器人则是要在不经过障碍物格子的前提下清理掉房间内的灰尘。
1501 0
二分法查找
版权声明:本文为博主原创文章,转载请注明出处。 https://blog.
937 0
常用的消息摘要算法小总结
今天偶然的学习了一下几种关于消息摘要算法的知识。个人觉得很好。应着老话“好记性不如烂笔头”,我就码了几行代码咯。 算法嘛,没什么好说的了。毕竟是设计者智慧与汗水的结晶,也是时代进步的推动力。
1009 0
+关注
python之战
专注python学习与应用擅长爬虫、web、全栈,专注RPA技术实施;(个人公号:Python之战)
90
文章
0
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载