房地产网站建设存在问题,扶贫工作网站怎么做,项目立项流程,国内亲子游做的最好的网站目录
1、概念
2、思路
3、实现算法 1、概念
二分查找又称折半查找#xff0c;它是一种效率较高的查找方法
原理#xff1a;首先#xff0c;假设表中元素是按升序排列#xff0c;将表中间位置记录的关键字与查找关键字比较#xff0c;如果两者相等#xff0c;则查找成…目录
1、概念
2、思路
3、实现算法 1、概念
二分查找又称折半查找它是一种效率较高的查找方法
原理首先假设表中元素是按升序排列将表中间位置记录的关键字与查找关键字比较如果两者相等则查找成功否则利用中间位置记录将表分成前、后两个子表如果中间位置记录的关键字大于查找关键字则进一步查找前一子表否则进一步查找后一子表。重复以上过程直到找到满足条件的记录使查找成功或直到子表不存在为止此时查找不成功。
2、思路
二分查询思想如下
取左left、右边界right以及左右边界的中间值index
如果所求的值小于索引index对应的值:
将右边界right赋值为index-1,因为此时index所对应的值是大于所求值num所以可以直接排除index.
赋值之前 赋值之后 如果所求索引的值大于索引值index对应的值
将左边界left赋值为index1,因为此时index所对应的值是小于所求值num所以可以直接排除index.
赋值之前 赋值之后
理论同上不再画图可以看下面二分查找的动画 如果index对应的值和num的值相等
所求值对应的索引就是index.
时间复杂度O(logn)对长度为 n 的数组进行二分最坏情况就是取 2 的对数。 空间复杂度O(1)无额外空间
3、实现算法
3.1递归代码实现二分查找算法 def binary_search(alist, item):if len(alist) 0:return Falseelse:midpoint len(alist)//2 #中间索引值if 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))3.2 非递归的方式
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))面试题口诀
1.奇数二分取中间。
2.偶数二分取中间左边。
面试题
1有一个有序表为15811192231354045484950 。当二分查找值为48的节点时查找成功需要比较的次数是 2在拥有512个元素的数组中二分查找一个数需要比较的次数最多不超过多少次。
解题方法1
用512/2/2/2…直到最终等于1中间除了几次2就是几次。
解题方法2
2^n 512 求解n的值即可。
解体方法3: 如果结果为整数即为最终答案。
如果是小数则舍弃小数部分整数再加1为最终结果。
