本章主要講述 【用pythonWrite a linear search and binary search】
Has been a long time ago withJava寫過了,為什麼要改用python寫？
javaIs written by college,Long time no reviewjava了,And the interview is to：手撕代碼,我目前對python比java熟,雖然Algorithm ideas are the same,But still want to take beforejava寫的用python寫一遍
Java語言編寫：https://blog.csdn.net/Makasa/article/details/90741952
"""
這裡寫pythonGrammar of linear search,和二分查找
"""
list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
def linear_search(target_val):
"""
線性查找
時間復雜度為O(n)：Sequential search is to find the list from the beginning to the end,最多找n次
:return:
"""
# enumerate()函數一般用於for循環中,可拿到index和index對應的值
# enumerate(sequence, start])：
# 參數： sequence ： 一個序列、迭代器或其他支持迭代對象.
# start ： 下標起始位置的值. 例如可以從1The subscript began to check
for index, value in enumerate(list):
if value == target_val:
print("Find the value of the index is：", index)
return index
else:
return None
def binary_search(target_val):
"""
二分查找：Simply means you have a list of,Each cut a knife to get the intermediate value index in the middle,
1、If the target value of the intermediate and the same,To find back the intermediate value
2、If the intermediate value > 目標值,Is the intermediate value on the right side of the target,我們更改一下end_index為mid+1
3、If the intermediate value < 目標值,Is the intermediate values on the left side of the target,我們更改一下begin_index為mid+1
二分查找的復雜度O(logn)
注意：Binary search request list must be【有序列表】,二分查找速度快,But must sort.Sort of time complexity thanO(n).
:return:
"""
begin = 0
end = len(list) - 1
while begin <= end:
# An error on pit：Python中的 " / " 與 Java和CThe function of language is not the same,Python裡是取到的小數,並非是整數
# 如果想取整數,需要用 " // "
# Only the initial index less than or equal to the final indexes,Only to find
mid = (begin + end) // 2
if list[mid] == target_val:
# 1、If the target value of the intermediate and the same,To find back the intermediate value
print("Eventually find element index is：", mid)
return mid
elif list[mid] > target_val:
# 2、If the intermediate value > 目標值,Is the intermediate value on the right side of the target,我們更改一下end_index為mid + 1
end = mid - 1
else:
# 3、If the intermediate value < 目標值,Is the intermediate values on the left side of the target,我們更改一下begin_index為mid+1
begin = mid + 1
else:
print("The current list of no value")
return None
if __name__ == '__main__':
linear_search(target_val=5)
binary_search(target_val=5)
