【数据结构与算法】python实现二分查找

文章目录

• 一、二分查找的基本概念
• 二、二分查找过程
• 三、python实现二分查找的两种方式
• • 递归代码实现二分查找算法
  • 非递归的方式实现二分查找算法
  • 三、���展：二叉树反推

    一、二分查找的基本概念

    二分查找又称折半查找，它是一种效率较高的查找方法

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

      二、二分查找过程

      查找数字: 1

      • 第一步: 找到中值(取整数)
      • 第二步: 要查找的数和中值比较
      • 第三步: 若小于中值则在中值前面找，若大于中值则在中值后面找，等于中值时直接返回

        三、python实现二分查找的两种方式

        递归代码实现二分查找算法

           def binary_search(alist, item):       if len(alist) == 0:           return False       else:           midpoint = len(alist)//2           if alist[midpoint]==item:             return True           else:             if item