面试必备算法|二分查找的思想和实现(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 item < alist[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
    return found


binarySearch([2, 4, 5, 7, 8], 5)

二分查找的递归实现

# 递归实现
def binarySearch(alist, item):
    if len(alist) == 0:
        return False
    else:
        midpoint = len(alist) // 2
        if alist[midpoint] == item:
            return True
        else:
            if item < alist[midpoint]:
                return binarySearch(alist[:midpoint], item)
            else:
                return binarySearch(alist[midpoint + 1:], item)


binarySearch([2, 4, 5, 7, 8], 5)
相关文章
|
3天前
|
算法
递归算法实现二分查找
本文简要介绍了递归实现的二分查找算法,这是一种在有序列表中快速查找的策略。递归方法虽在实际应用中较少,但有助于理解递归思想,为学习数据结构中的树内容打下基础。文中提供了原版和递归版本的二分查找代码,并强调了递归算法中处理未找到情况的注意事项。此外,还提到了递归在解决复杂问题时的优势,并通过链接分享了一个关于递归实现素数判断的例子。
10 2
|
4天前
|
算法 索引
【数据结构与算法 | 基础篇】力扣704/35/34:二分查找
【数据结构与算法 | 基础篇】力扣704/35/34:二分查找
|
6天前
|
机器学习/深度学习 算法 固态存储
深度学习算法工程师面试问题总结| 深度学习目标检测岗位面试总结
本文给大家带来的百面算法工程师是深度学习目标检测岗位面试总结,文章内总结了常见的提问问题,旨在为广大学子模拟出更贴合实际的面试问答场景。在这篇文章中,我们还将介绍一些常见的深度学习目标检测面试问题,并提供参考的回答及其理论基础,以帮助求职者更好地准备面试。通过对这些问题的理解和回答,求职者可以展现出自己的深度学习目标检测领域的专业知识、解决问题的能力以及对实际应用场景的理解。同时,这也是为了帮助求职者更好地应对深度学习目标检测岗位的面试挑战,提升面试的成功率和竞争力。
|
6天前
|
算法 搜索推荐 索引
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(下)
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题
12 0
|
7天前
|
SQL 分布式计算 前端开发
10个常见的python面试问题_python面试常见问题
10个常见的python面试问题_python面试常见问题
|
7天前
|
算法 程序员 索引
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(中)
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题
16 0
|
7天前
|
算法 C语言 C++
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(上)
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题
12 0
|
7天前
|
存储 数据可视化 算法
最新Python-Matplotlib可视化(9)——精通更多实用图形的绘制,2024年最新小米面试题库
最新Python-Matplotlib可视化(9)——精通更多实用图形的绘制,2024年最新小米面试题库
最新Python-Matplotlib可视化(9)——精通更多实用图形的绘制,2024年最新小米面试题库
|
7天前
|
数据采集 Java 数据挖掘
最新Python+OpenCV+dlib汽车驾驶员疲劳驾驶检测!,2024年最新网易云java面试
最新Python+OpenCV+dlib汽车驾驶员疲劳驾驶检测!,2024年最新网易云java面试
最新Python+OpenCV+dlib汽车驾驶员疲劳驾驶检测!,2024年最新网易云java面试
|
7天前
|
数据采集 算法 网络协议
最新Python 面试常见问题(1),2024年最新面试官必问的10个问题
最新Python 面试常见问题(1),2024年最新面试官必问的10个问题
最新Python 面试常见问题(1),2024年最新面试官必问的10个问题