查找
目錄
- 查找
- 順序查找
- 二分查找
在一些資料元素中，通過一定的方法找出與給定關鍵字相同的資料元素的程序叫做查找
串列查找（線性表查找）：從串列中查找指定元素
——輸入：串列、代查找元素
——輸出：元素下標（未找到元素是一般回傳None）
內置串列查找函式：index()
順序查找
定義：也叫線性查找，從串列第一個元素開始，順序進行搜索，直到找到元素或搜索到串列最后一個元素為止
這個很好理解，就直接上代碼吧，
代碼展示：
def linear_search(li, val):
for ind, v in enumerate(li):
if v == val:
return ind
else:
return None
二分查找
定義：又叫折半查找，從有序串列的初始候選區li[0:n]開始，通過對待查找的值與候選區中間值的比較，可以使候選區減少一半
強調： 二分查找必須是有序的
舉個例子：
首先要是輸入想要查找的元素
在有序的串列中，將最左邊下標元素定義為left，最右邊元素下標定義為right，mid表示為中間的元素下標，即(left+right)//2
比較mid下標對應的元素與待查找元素的大小，此時代查找元素比mid對應的元素小，所以我們知道待查找元素可能出現在mid的左側候選區，然后將right的下標更新為此時候選區的最右側下標，即為mid-1
此時mid的下標也更新為新的(left+right)//2
再次比較mid下標對應的值與待查找值的大小，發現mid對應的值比待查找值小，由此可知待查找值可能存在于mid的右側，然后將left移到右側候選區的最左邊
然后更新mid，發現mid和left指向相同，因此找到了待查找的值并回傳mid
代碼展示：
def binary_search(li, val):
left = 0
right = len(li)-1
while left <= right:
mid = (left + right) // 2
if li[mid] == val:
return mid
elif li[mid] > val: #帶查找的值在mid左側
right = mid -1
else:
left = mid + 1
else:
return None
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/244711.html
標籤：其他
上一篇：手游作弊(二)-記憶體讀寫實體
下一篇：c++入門：分享一些實用的函式