1.二分查找：适用于查找有序元素列表中的指定元素
特点：列表必须有序 对半拆分
问题：游戏 1-100中，小明设置一个数字，小红猜测，数字=小明设置正确，数字<小明设置 小明说小了 ，数字>小明设置 小明说大了，最多多少次小红能猜中数字？
使用折半法查找
第一步 100/2 =50 猜50
第二步 50/2 猜25
第三步 25/2 猜13
第四步 13/2 猜7
第五步 7/2 猜4
第6步 4/2 猜2
第7步 2/2 猜1
所以最多7步之内，肯定能得到答案
对于任意n个元素的有序序列，查找的步骤最多是
k即为最大次数
log是什么？ log是对数表达式，那对数是什么？ 对数运算是幂运算的逆运算
首先幂运算 比如 10*10=100 即
反过来 求x的值即为对数运算， 数学表达式为是
以下为二分查找python版代码表达式
# 循环
def brinary_search_(array, find):
low = 0
height = len(array) - 1
while low <= height:
mid = int((height + low) / 2)
if array[mid] == find: # 比较完中间值 后面无需再比较所以 mid的位置根据情况+1 or -1
return mid
if array[mid] > find:
height = mid - 1
else:
low = mid + 1
return -1
# 递归
def brinary_search(array, find, low, height):
mid = int((height + low) / 2)
if find > array[height] or find < array[low]:
return -1
if array[mid] == find:
return mid
if low > height:
return -1
if array[mid] > find:
return brinary_search(array, find, low, mid - 1)
if array[mid] < find:
return brinary_search(array, find, mid + 1, height)
if __name__ == '__main__':
myArray = [1, 3, 5, 7, 8, 10, 12]
index = brinary_search_(myArray, 6)
index_ = brinary_search(myArray, 8, 0, len(myArray) - 1)
print(index)
print(index_)
