本章主要講述 【用python編寫線性查找和二分查找】
很久以前其實已經用Java寫過了，為什麼要改用python寫？
java是大學時期寫的，很長時間沒復習java了，而目前面試其實都要：手撕代碼，我目前對python比java熟，雖然算法的思路都是一樣的，但是還是想把之前用java寫的用python寫一遍
Java語言編寫：https://blog.csdn.net/Makasa/article/details/90741952
"""
這裡寫python語法的線性查找，和二分查找
"""
list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
def linear_search(target_val):
"""
線性查找
時間復雜度為O(n)：順序查找是把列表從頭到尾查找一遍，最多找n次
:return:
"""
# enumerate()函數一般用於for循環中，可拿到index和index對應的值
# enumerate(sequence, start])：
# 參數： sequence ： 一個序列、迭代器或其他支持迭代對象。
# start ： 下標起始位置的值。 例如可以從1下標開始查
for index, value in enumerate(list):
if value == target_val:
print("找到的值的索引是：", index)
return index
else:
return None
def binary_search(target_val):
"""
二分查找：簡單來說就是你有一個列表，每次在中間切一刀拿到中間值索引，
1、如果這個中間值和目標值相同，就找到返回這個中間值
2、如果這個中間值 > 目標值，也就是中間值在目標值的右邊，我們更改一下end_index為mid+1
3、如果這個中間值 < 目標值，也就是中間值在目標值的左邊，我們更改一下begin_index為mid+1
二分查找的復雜度O(logn)
注意：二分查找要求列表必須是【有序列表】，二分查找速度快，但是必須排序。排序的時間復雜度大於O(n)。
:return:
"""
begin = 0
end = len(list) - 1
while begin <= end:
# 踩坑報錯點：Python中的 " / " 與 Java和C語言裡的作用是不一樣的，Python裡是取到的小數，並非是整數
# 如果想取整數，需要用 " // "
# 只有初始索引小於等於最後索引時，才去進行查找
mid = (begin + end) // 2
if list[mid] == target_val:
# 1、如果這個中間值和目標值相同，就找到返回這個中間值
print("最終找到的元素索引是：", mid)
return mid
elif list[mid] > target_val:
# 2、如果這個中間值 > 目標值，也就是中間值在目標值的右邊，我們更改一下end_index為mid + 1
end = mid - 1
else:
# 3、如果這個中間值 < 目標值，也就是中間值在目標值的左邊，我們更改一下begin_index為mid+1
begin = mid + 1
else:
print("當前列表沒有值")
return None
if __name__ == '__main__':
linear_search(target_val=5)
binary_search(target_val=5)
