西安网站推广慧创科技,郑州信息网官网,网站空间网站虚拟空间,网站开发协议文章目录 一、二分查找的基本概念二、二分查找过程三、python实现二分查找的两种方式#x1f347;递归代码实现二分查找算法#x1f955;非递归的方式实现二分查找算法 三、拓展#xff1a;二叉树反推 一、二分查找的基本概念
二分查找又称折半查找#xff0c;它是一种效率… 文章目录 一、二分查找的基本概念二、二分查找过程三、python实现二分查找的两种方式递归代码实现二分查找算法非递归的方式实现二分查找算法 三、拓展二叉树反推 一、二分查找的基本概念
二分查找又称折半查找它是一种效率较高的查找方法
原理首先假设表中元素是按升序排列将表中间位置记录的关键字与查找关键字比较如果两者相等则查找成功否则利用中间位置记录将表分成前、后两个子表如果中间位置记录的关键字大于查找关键字则进一步查找前一子表否则进一步查找后一子表。重复以上过程直到找到满足条件的记录使查找成功或直到子表不存在为止此时查找不成功。
二、二分查找过程 查找数字: 1 第一步: 找到中值(取整数)第二步: 要查找的数和中值比较第三步: 若小于中值则在中值前面找若大于中值则在中值后面找等于中值时直接返回
三、python实现二分查找的两种方式
递归代码实现二分查找算法 def binary_search(alist, item):if len(alist) 0:return Falseelse:midpoint len(alist)//2if alist[midpoint]item:return Trueelse:if itemalist[midpoint]:return binary_search(alist[:midpoint],item)else:return binary_search(alist[midpoint1:],item)testlist [0, 1, 2, 8, 13, 17, 19, 32, 42,]print(binary_search(testlist, 3))print(binary_search(testlist, 13))非递归的方式实现二分查找算法
def binary_search(alist, item):first 0last len(alist)-1while firstlast:midpoint (first last)/2if alist[midpoint] item:return Trueelif item alist[midpoint]:last midpoint-1else:first midpoint1return False
testlist [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binary_search(testlist, 3))
print(binary_search(testlist, 13))三、拓展二叉树反推 我们如何根据提供的三种深度排序中的两种排序反推出来二叉树的图呢 反推原理先根中定边往复树两边 举例说明如 先序0 1 3 7 8 4 9 2 5 6 中序7 3 8 1 9 4 0 5 2 6
1、先序找根中序定两边 先序的特点是第一个元素是根中序的特点是根两侧分别是左右子树所以我们反推分界初始图
2、两边重复步骤1 根据中序的内容我们确定了两个子树包含的内容那么结合先序的特点两个范围内首先出现的数字就是第一层的节点内容 所以左侧子树的根节点是1右侧子树的根节点是2 3、两边重复步骤1和2
找到左侧子树的根节点是1 那么结合中序的左侧子树内容7 3 8 1 9 4可以确定左侧子树包括
左部分738右部分94
结合先序的左侧子树内容1 3 7 8 4 9可以确定左侧子树的1元素的两个子节点是3和9
找到右侧子树的根节点是2
结合中序的右侧子树内容5 2 6结合先序的右侧子树内容2 5 6
可以确定2节点的左侧元素是5右侧元素是6
4、重复步骤3 对于3结点来说
结合中序的内容7 3 8结合先序的内容3 7 8 可以确定3节点的左侧元素是7右侧元素是8
对于9结点来说
结合中序的内容9 4结合先序的内容4 9
可以确定9节点的左侧元素是4
所以最终的二叉树图是
