資源簡介

(共19張PPT)
數據查找
情景導入1
打亂的撲克牌
請在打亂的撲克牌中尋找出下面這張牌，講一講你尋找的方法
查找（Search）又稱檢索，是計算機根據所給條件查找出滿足條件的對象，即在存儲的一批數據內尋找出一個特定的數據，或者確定在該批數據內是否存在這樣的數據。
查找的定義
常用查找算法：
順序查找和對分查找
順序查找——算法思想
算法思想
順序查找又稱線性查找，從順序表的一端開始，依次將每個元素的關鍵字與給定值key（查找鍵）進行比較。
若某個元素的關鍵字等于key，則表明查找成功；若所有元素都比較完畢仍找不到，則表明查找失敗。
在不考慮撲克牌花色的情況下，僅在A到K,13張撲克牌中尋找指定的牌。撲克牌2～ 10 為數字本身,A 為 1 ,J 為 11 ,Q 為 12 ,K 為 13，變量Key存儲要查找的牌。
順序查找——算法描述
將代表13張撲克牌對應的數字存儲于數組d中， 要查找的撲克牌對應數字儲于變量key中。
② 依次將d數組中元素與key進行比較。
③ 若數組中某個數與key相等則查找成功并結束查找，若所有元素比較完畢仍找不到，則查找失敗。
枚舉算法
順序查找——算法演示
d[0] d[1] d[2] d[3] d[4] d[5] d[6] d[7] d[8] d[9] d[10] d[11] d[12]
11 12 13 4 10 6 7 8 9 5 1 2 3
key=4
①i=0，d[0]=11 !=key
②i=1，d[1]=12 !=key
③i=2，d[2]=13 !=key
④i=3，d[3]=4 ==key→查找成功
問題：
若將上述問題規模擴大，在n張牌中尋找，則最理想情況是查找_______次？最差的情況需要查找________次？平均查找次數：________
1
n
(n+1)/2
順序查找——程序實現
For i in range(___________):
If :
________________
else:
________________
0,n,1
d[i]==key
print(i)
①遍歷數組的索引。
②如果找到，輸出下標，結束查找。
③若找不到，提示“沒找到”
break
print(“沒找到”)
順序查找——小結
1.順序查找本質上是一種__________思想，順序查找程序就是用循環來枚舉所有要查找的對象，然后在循環體內用條件判斷當前枚舉出的對象是否等于查找對象。
2.當需要查找的數據規模為 n 時，順序查找最少查找____ 次，最多查找_____次，其平均查找次數是________。
3.順序查找最大的優點是查找的數據可以是亂序的，但是其缺點是查找效率太低。順序查找將待查找的數值與序列中的數逐個進行比較，直到找出與給定數值相同的數為止，其時間復雜度為_____ 。
枚舉算法
1
n
(1+n)/2
O(n)
新打開的撲克牌
請在新打開的撲克牌中尋找出下面這張牌，講一講你尋找的方法
情景導入2
對分查找——算法思想
算法思想
首先將查找的數與有序數組內處于中間位置的數據比較，如果中間位置上的數與查找的數不同，則根據數組的有序性，確定應該在數組的前半部分還是后半部分繼續查找。在新確定的范圍內，繼續按上述方法，直到獲得最終結果。
對分查找——算法描述
將13張撲克牌對應的數字（升序）存儲于數組d中， 要查找的撲克牌對應數字儲于變量key中。
② 依次將d數組查找區間中間位置的數mid與key進行比較。
③ 若mid與key相等則查找成功，結束查找,若key大于mid下一次查找區間為右半部分，反之為左半部分。重復②③兩個步驟直到區間元素個數為零，即查找失敗。
在不考慮撲克牌花色的情況下，僅在A到K,13張升序排列的撲克牌中尋找指定的牌。撲克牌2～ 10 為數字本身,A 為 1 ,J 為 11 ,Q 為 12 ,K 為 13，變量Key存儲要查找的牌。
對分查找——算法演示
d[0]
d[1]
d[2]
d[3]
d[4]
d[5]
d[6]
....
d[12]
←i
←j
←mid
第1次查找：
范圍為__________，i=________，j=_____，mid=___________。d[mid]=__________。
d[mid]_____key=5？
:后續查找的范圍應該是_______________。
d[0]~d[12]
0
12
(0+12)//2=6
d[6]=7
>
d[0]~d[5]
1
2
3
4
5
6
7
...
13
i：查找數組的起點索引值；
j：查找數組的終點索引值；
mid=（i+j）//2，查找數組的中間位置的索引值。
對分查找——算法演示
d[0]
d[1]
d[2]
d[3]
d[4]
d[5]
←i
←j
←mid
第2次查找：
范圍為__________，i=________，j=_____，mid=___________。d[mid]=__________。
d[mid]_____key=5？
:后續查找的范圍應該是_______________。
d[0]~d[5]
0
5
(0+5)//2=2
d[2]=3
<
d[3]~d[5]
1
2
3
4
5
6
對分查找——算法演示
d[3]
d[4]
d[5]
←j
←mid
第3次查找：
范圍為__________，i=________，j=_____，mid=___________。d[mid]=__________。
d[mid]_____key=5？
查找成功，結束查找。
d[3]~d[5]
3
5
(3+5)//2=4
d[4]=5
==
4
5
6
←i
對分查找——流程圖描述
開始
i=0,j=12
d[mid]=key
d[mid]查找成功
查找失敗
結束
Y
N
Y
N
Y
N
mid
i<=j
=(i+j)//2
i=mid+1
j=mid-1
對分查找——程序實現
key=int(input())；f=False；i=0 #所有數據（升序）存儲在數組d中
j=
while :
mid=
if d[mid]==key:
f=True
break
if d[mid]>key:
else:
if f==True:
print("查找成功！下標為"+str(mid))
else:
print("沒有找到！")
i<=j
(i+j)//2
j=mid-1
i=mid+1
①給i,j賦初值
②當i<=j時表示區間內元素個數不為零，重復執行查找工作
③計算查找區間中間位置mid
④判斷中值是否就是查找鍵key
⑤如果中值不是查找鍵，則判定下一個查找范圍應該在左半部分還是在右半部分。注意i和j的控制。
⑥輸出查找結果：f=True,mid中存儲的即為查找鍵Key在數組 d中的位置，f=False表示查找鍵key在數組d中不存在。
len(d)-1
對分查找——二叉排序樹
7
3
1
5
4
6
2
10
8
9
12
11
13
二叉排序樹：
①若左子樹不為空，則左子樹的值均小于它的根節點的值.
②若右子樹不為空，則右子樹的值均大于它的根節點的值
③它的左右子樹也分別為二叉排序樹。
13張撲克牌使用對分查找過程我們可以用一棵二叉樹來表示。
假設對分查找數據規模為n最多查找次數？
最多查找次數為二叉數高度：int(log2n)+1。
查找算法小結
查找算法 順序查找 對分查找
優點 ①算法簡單，對數據是否有序沒有要求。 ②查找效率高，適用于大數據查找。
缺點 ②查找效率較低，當數據量大時不宜使用。 ①要求被查找數據必須有序。
查找次數 一般情況是，當需要查找的數據規模為 n 時，順序查找最少查找____次，最多查找____次，其平均查找次數是________。 當需要查找的數據規模為 n 時，最少查找 次，最多進行_____________次查找。
算法思想 順序查找本質上是一種_______算法思想。 對分查找思想符合_______算法的思想。
1
n
(n+1)/2
int(log2n)+1
枚舉
遞歸
1
查找的定義。
課堂小結
順序查找算法思想、程序實現。
對分查找算法思想、程序實現。
順序查找與對分查找算法的優缺點。

展開更多......

收起↑