算法之二分查找法个人笔记

什么是二分查找？

概念：

就像是我们查字典一样。如果我们要找以O开头的词，我们肯定会直接从字典最中间开始往后面翻，而不是从A开始一个一个往后面找。

比起一个一个的查询，二分查找法明显更节约时间。

要求：

输入的列表需要按大小顺序排列。
尤其在意细节，比如是否加等于，+-1等，注意列表下标和for循环的range。
不能出现目标值重复现象。

简单的代码实现

def binary_search(list: list, x: int):
    low = 0 # 最小值点
    high = len(list)-1# 最大值点
    while low<=high:
        mid = (low+high)//2
        xg = list[mid]# 中间值
        if xg > x:
            high = mid - 1
        elif xg < x:
            low = mid + 1
        else:
            return mid
    return -1

途中出现的问题：

为什么是high = mid-1和low = mid + 1?

如果我们不加减1，当我们查询的元素是列表最后一位或者查询元素不在列表里面，代码会陷入死循环。

为什么会出现这样的错误？举个例子，若列表为[6,7]，此时：low = 0,high = 1，mid = 0。如果不+-1，low就一直<=high。

那为什么是high=mid-1呢？当我们已经把x_guess（中间值）和x相比较之后，mid已经被比较过，比mid还小那么就要在low和mid-1的区间比较。

low = mid+1同理。

为什么是while low <=high？

看你需求。如果是while low < high，那么所表示的是一个不包含最前面和最后面的开区间。最后和最前没法被索引到。

报错“unexpected EOF while parsing”

语法写错了

如何让使用者输入列表和待找值？为啥不能用print(binary_search(input(),input()))？

input()语句输入的内容只能是字符串类型。

一般来说如果我们想把它转为数字，应该输入int(input())这样的代码。

如何输入列表？

常用：

1	list(evel(input("请输入列表,数字用,隔开")))

eval()函数

作用：将字符串转为python语句（就是去掉“”）然后执行转化后的语句

例：

a = 1
b = 2
c = eval("a+b")
print(c)
#结果为3

使用input()函数输入，数据会以字符串的形式返回。如果我们输入的是需要参与计算的数字，则还需要转换类型，有了eval()函数，我们可以这样做：

1	eval(input("请输入数字"))

list()函数

作用：把元组/字符串/字典/集合以及其他可迭代序列转化为list

算法：二分查找