二分法查找

查找

查找要学习的主要内容有两个：顺序查找和二分法查找。

数据准备

import random as r
n = int(input("请输入列表元素的个数："))
lst = []
for i in range(n):
    a = r.randint(-200, 200)
    while a in lst:
        a = r.randint(-200, 200)
    lst.append(a)

顺序查找

顺序查找也叫线性查找，是指按一定的顺序检查列表中每一个元素，直到找到所要寻找的特定值为止。这里需要对列表的值进行循环遍历：

def sequence_search(ls, x):
    for i in ls:
        if i == x:
            return True
    return False

if sequence_search(lst, 100):
    print("100找到了。")
else:
    print("没有在列表里找到100")

二分法查找的主要思想就是将列表进行折半查找，通过不断折半的过程来确定要查找的关键字所在的区域。

先将列表进行正序排序;
设置起始和末尾结点start、end，然后得到中间结点mid， mid = (start + end) // 2;
如果中间结点的值大于要查找的关键字key，则设置end = mid - 1，反之，如果中间结点的值小于要查找的关键字key，则设置start = mid + 1;
再次计算mid = (start + end) // 2;
重复3和4直到找到关键字或者start和end相遇。

key = 
lst.sort()
start = 0
end = len(lst) - 1
flag = False

while start < end:
    mid = (start + end) // 2
    if lst[mid] > key:
        end = mid - 1
    elif lst[mid] < key:
        start = mid + 1
    else:
        flag = True
        break

if flag:
    print(key)
else:
    print('Not found.')

def binary_search(ls, key):
    ls.sort()
    start = 0
    end = len(ls) - 1
    mid = (start + end) // 2
    while start < end:
        if ls[mid] > key:
            end = mid - 1
        if ls[mid] < key:
            start = mid + 1
        if ls[mid] == key:
            return True
        mid = (start + end) // 2
    return False

利用二分法查找求平方根

要利用二分法的算法求平方根，需要注意的是一个正数的平方根是一定存在的，假设求一个有两位小数的平方根，大致的步骤如下：

设置起始和末尾节点start、end，如果这个数key大于1, 则start = 1，end = key; 如果key小于1，则start = key， end = 1；
计算mid = (start + end) / 2
如果mid * mid的结果与key的差值的绝对值小于0.0001，则确定mid为key的平方根；
如果mid * mid大于key，则设置end = mid，反之设置start = mid;
再次计算mid = (start + end) / 2;
重复4和5直到找到平方根为止。

key = float(input("请输出一个有两位小数的浮点数："))

if key > 1:
    start = 1
    end = key
else:
    start = key
    end = 1
mid = (start + end) / 2

while abs(mid * mid - key) > 0.0001:
    if mid * mid > key:
        end = mid
    if mid * mid < key:
        start = mid
    mid = (start + end) / 2

print(round(mid, 2))