二分查找基本原理

1.二分查找

1.1 基本概念

• 二分法(折半查找）是一个查找算法
• 要求：数据必须是有序列表
• 核心思想：掐头结尾取中间

1.2 二分查找查找步骤

1.2.1 中间索引不能整除，取整数作为中间索引

1.2.2 索引不能整除，整数+1作为中间索引

1.3 二分查找大O记法表示

元素个数	步骤次数
2	1
4	2
8	3
16	4
N	$lo{g}_2^N$

• 二分查找大O记法表示:$lo{g}_2^N$
  • 意味着该算法当数据量翻倍时，步数加 1。

2. 二分查找代码实现

# 方式一
lis = [1, 12, 14, 15, 23, 35, 435, 567, 578, 656, 789, 1234]
n = int(input('请输入你要查找的数：'))
left = 0
right = len(lis) - 1
while left <= right:middle = (left + right) // 2print(f"当前中间索引为{middle}，值为{lis[middle]}")if n > lis[middle]:left = middle+1elif n < lis[middle]:right = middle-1else:print('找到了,他在索引为%s位置' % middle)break
else:print('没有这个数据')# 方式二
lis = [1, 12, 14, 15, 23, 35, 435, 567, 578, 656, 789, 1234]
n = int(input('请输入你要查找的数：'))
left = 0
right = len(lis) - 1
while left <= right:middle = (left + right) // 2if (left + right) % 2 != 0:middle = ((left + right) // 2)+1print(f"当前中间索引为{middle}，值为{lis[middle]}")if n > lis[middle]:left = middle+1elif n < lis[middle]:right = middle-1else:print('找到了,他在索引为%s位置' % middle)break
else:print('没有这个数据')