二分查找

• 1. 順序查找
• 2. 二分查找

1. 順序查找

順序查找就是從列表的第一項開始，依次進行搜索，一直到列表最後或者找到元素為之。

例：從列表中按照順序查找一個數字，存在返回下標，否則返回None

# 在一個列表中查找一個數,
# 如果存在返回該數字的下標,否則返回None
def f(data_list, value):
for i in data_list:
if value == i:
return data_list.index(i)
break
else:
return None
data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(f(data, 6)) # 輸出5
print(f(data, 15)) # 輸出None

2. 二分查找

注意：列表必須有序

思路：

1. 先給定一個范圍 比如：1-100
2. 先找這個范圍的一半mid,也就是數字50（下標為49）
3. 如果找大了,則將最大范圍設為 mid-1,此時范圍為數字1-49（下標范圍：0-48）
4. 如果找小了,則將最小范圍設為 mid+1,此時范圍為數字50-100（下標范圍：51-100）
5. 重復2-4步驟,直到找到這個數字

例如：在1到100之間找1，會先找中間下標49，如果找大了 就往mid右邊找，如果找的小了 就往mid左邊找

data_list = [i for i in range(1, 101)] # 帶查找的列表
value = 2 # 要查找的數
left = 0 # 最左邊下標
right = len(data_list) - 1 # 最右側下標
x = 1
while left <= right: # 左邊下標小於右邊下標，在列表這個范圍找
mid = (left + right) // 2 # 整除，取中間下標位置
print('\n第{}次，取中間的下標為:{}'.format(x, mid))
if data_list[mid] == value: # 如果要查找的數字等於中間位置的數字時，則打印該索引
print('這個數的下標為：', mid)
break
elif data_list[mid] > value:
right = mid - 1
else:
left = mid + 1
print('\t\tleft：{}， right:{}'.format(left, right))
x += 1
else:
print(None)

def search(data_list, value):
""" :param data_list: 待查找的列表 :param value: 要查找的數字 :return:下標或None """
left = 0 # 列表最左邊下標
right = len(data_list) - 1 # 列表右邊下標
while left <= right: # 左邊下標小於右邊下標，在列表這個范圍找
mid = (left + right) // 2 # 整除，取中間下標位置
if data_list[mid] == value: # 如果要查找的數字等於中間位置的數字時，則返回該索引
return mid
elif data_list[mid] > value:# 如果mid大於要查找的數，將right重新賦值為中間下標的左側(也就是mid-1)
right = mid - 1
else:
left = mid + 1
# print('mid:{}, left：{}，right:{}'.format(mid, left, right))
else:
return None
a = [i for i in range(100)]
print(search(a, 2))