Python算法實踐Week4-查找算法

0x01 列表

列表：數據序列，是能存儲多個數據的連續存儲空間。

• 列表的創建

a_list = [1,2,3]
a_list = ['this','is','a','list']
a_list = ['this','is','test',1,2,3]
a_list = list('hello')
# ['h', 'e', 'l', 'l', 'o']
a_list = list(range(1,20,2))
# [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

• 列表的訪問

a_list = ['this','is','a','list']
print(a_list[0])
# this
print(a_list[-1])
# list
print(a_list[5])
# IndexError: list index out of range
print(a_list[1:3])
# ['is', 'a']
print(a_list[1:])
# ['is', 'a', 'list']

• 列表的遍歷

a_list = ['this', 'is', 'a', 'list']
for x in a_list:
print(x)
for i in range(len(a_list)):
print(a_list[i])

0x02 順序查找

• 基本實現

list = list(range(1,20,2))
# [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
x = int(input('請輸入要查找的整數：'))
for i in range(len(list)):
if i == x:
print('找到了，整數{}在列表中'.format(x))

• 進行優化，增加查找不到時的反饋

list = list(range(1, 20, 2))
print(list)
# [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
sign = False
x = int(input('請輸入要查找的整數：'))
for i in range(len(list)):
if list[i] == x:
print('找到了，整數{}在列表中'.format(x))
sign = True
if not sign:
print('沒找到啊')

• 數據查找相關函數

# 數據查找相關函數
list = list(range(1, 20, 2))
# [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(list.index(13))
# 6
# 返回第一個數據為13的下標
print(list.index(15, 2, 10))
# 7
# 返回2到9(10-1)之間第一個數據為15的下標
temp_list = [1, 1, 1, 1, 1, 2, 3]
print(temp_list.count(1))
# 5
# 返回數據為1的個數

• 使用內置函數實現上述順序查找算法

list = [1, 2, 2, 3, 3, 3, 4, 4, 5, 6]
x = int(input('請輸入要查找的整數x:'))
n = list.count(x)
if n == 0:
print('沒找到{}'.format(x))
else:
j = 0
for i in range(n):
j = list.index(x, j, len(list)) + 1
# 指定范圍進行查找
print('找到了，第{}個數是{}'.format(j, x))

0x03 二分查找

• 二分查找與順序查找對比
• python實現

# 二分查找
list = list(range(1, 20, 2))
# [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
x = int(input('請輸入要查找的整數：'))
start = 0
end = len(list) - 1
while start <= end:
mid = (start + end) // 2
if list[mid] == x:
break
elif x < list[mid]:
end = mid - 1
else:
start = mid + 1
if start <= end:
print('找到了，第{}個數是{}'.format(mid + 1, x))
else:
print('沒找到')

0x04 添加數據

• python實現

list = [1, 3, 5, 7, 9, 2, 4, -1, -1]
# 此處-1表示為空，表示占位符
x = int(input('請輸入整數x:'))
i = len(list) - 1
while i >= 0:
if list[i] != -1:
break
i -= 1
list[i + 1] = x
print(list)
# [1, 3, 5, 7, 9, 2, 4, 1, -1]

• 內置函數

# append(向列表尾部添加數據)
list = list(range(1,10,2))
# [1, 3, 5, 7, 9]
x = int(input('請輸入整數x:'))
list.append(x)
print(list)
# [1, 3, 5, 7, 9, 1]
# ---
# extend() 函數用於在列表末尾一次性追加另一個序列中的多個值（用新列表擴展原來的列表）。
list = list(range(1,10,2))
# [1, 3, 5, 7, 9]
list.extend([1,2,3])
print(list)
# [1, 3, 5, 7, 9, 1, 2, 3]
# ---
# insert() 函數用於將指定對象插入列表的指定位置。
list = list(range(1, 10, 2))
# [1, 3, 5, 7, 9]
list.insert(1, 100)
# list.insert(index, obj)
print(list)
# [1, 100, 3, 5, 7, 9]

0x05 刪除數據

• python實現

list = [1, 3, 5, 7, 9, 2, 4, 6, 8, 10]
x = int(input('請輸入要刪除的整數x:'))
n = len(list)
for i in range(n):
if list[i] == x:
list[i] = -1
print(list)
# [-1, 3, 5, 7, 9, 2, 4, 6, 8, 10]

• 列表刪除操作內置函數

# pop() 函數用於移除列表中的一個元素（默認最後一個元素），並且返回該元素的值
list = [1, 3, 5, 7, 9]
list.pop()
# [1, 3, 5, 7]
# 默認刪除最後一個
list.pop(1)
# [1, 5, 7]
# 刪除列表第二個元素
# ---
# remove() 函數用於移除列表中某個值的第一個匹配項
list = [1, 3, 5, 7, 9]
list.remove(3)
# [1, 5, 7, 9]

• 問題：刪除所有重復元素

list = [1, 1, 1, 1, 1, 1, 3, 5, 5, 5, 5, 5, 5, 5, 7, 9]
x = int(input('請輸入要刪除的整數:'))
n = list.count(x)
# n為列表有多少個x，執行n次remove()函數即可刪除列表中所有x值
for i in range(n):
list.remove(x)
print(list)
# [3, 5, 5, 5, 5, 5, 5, 5, 7, 9]