二分查找算法(Python)

目录

1、概念

2、思路

3、实现算法

---

1、概念

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

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

2、思路

二分查询思想如下：

取左left、右边界right，以及左右边界的中间值index

如果所求的值小于索引index对应的值:

​ 将右边界right赋值为index-1,因为此时index所对应的值是大于所求值num，所以可以直接排除index.

赋值之前：

赋值之后：

如果所求索引的值大于索引值index对应的值：

​ 将左边界left赋值为index+1`,因为此时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 item<alist[midpoint]:return binary_search(alist[:midpoint],item)else:return binary_search(alist[midpoint+1:],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 first<=last:midpoint = (first + last)//2if alist[midpoint] == item:return Trueelif item < alist[midpoint]:last = midpoint-1else:first = midpoint+1return False
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binary_search(testlist, 3))
print(binary_search(testlist, 13))

面试题口诀：

1.奇数二分取中间。

2.偶数二分取中间左边。

面试题：

（1）有一个有序表为1，5，8，11，19，22，31，35，40，45，48，49，50 。当二分查找值为48的节点时，查找成功需要比较的次数是？

（2）在拥有512个元素的数组中二分查找一个数，需要比较的次数最多不超过多少次。

解题方法1：

用512/2/2/2…直到最终等于1，中间除了几次2就是几次。

解题方法2：

2^n = 512 ，求解n的值即可。

解体方法3:

​ 如果结果为整数，即为最终答案。

​ 如果是小数，则舍弃小数部分，整数再加1，为最终结果。