# 【wk14_1207】演算法_排序與搜尋
<pre>
8.3 搜尋
1. 循序搜尋
2. 二分搜尋
<pre/>

## 【inclass practice】

### {範例}
1. 由小排到大排序 \<bubble>
2. 追蹤泡沫排序法的過程 \<bubble_debuge>
3. 循序搜尋 : 中獎者姓名 \<sequential>
4. 二分搜尋 : 中獎者姓名 \<binary>

# 1.由小排到大排序 <bubble>
def switch(i) :
    datas[i], datas[i+1] = datas[i+1], datas[i]
datas = [3, 5, 2, 89, 41, 17]

print("排序前 :", datas)

n = len(datas)

for i in range(n-1) : # i介於 0~n-1
    #print(f"i = {i}, j = {j}", end = "")
    for j in range(0, n-1-i) :
        print(f"i = {i}, j = {j} : [j] = {datas[j]}, [j+1] = {datas[j+1]}", end = "")
        if datas [j] < datas [j+1] :
            switch(j)
            print(f"交換後 : [j] = {datas[j]}, [j+1] = {datas[j+1]}", end = "\n")
        else :
            print(f"不交換 \n")
    print(f"{datas} \n")

print("排序後 :", datas)

排序前 : [3, 5, 2, 89, 41, 17]
i = 0, j = 0 : [j] = 3, [j+1] = 5交換後 : [j] = 5, [j+1] = 3
i = 0, j = 1 : [j] = 3, [j+1] = 2不交換

i = 0, j = 2 : [j] = 2, [j+1] = 89交換後 : [j] = 89, [j+1] = 2
i = 0, j = 3 : [j] = 2, [j+1] = 41交換後 : [j] = 41, [j+1] = 2
i = 0, j = 4 : [j] = 2, [j+1] = 17交換後 : [j] = 17, [j+1] = 2
[5, 3, 89, 41, 17, 2]

i = 1, j = 0 : [j] = 5, [j+1] = 3不交換

i = 1, j = 1 : [j] = 3, [j+1] = 89交換後 : [j] = 89, [j+1] = 3
i = 1, j = 2 : [j] = 3, [j+1] = 41交換後 : [j] = 41, [j+1] = 3
i = 1, j = 3 : [j] = 3, [j+1] = 17交換後 : [j] = 17, [j+1] = 3
[5, 89, 41, 17, 3, 2]

i = 2, j = 0 : [j] = 5, [j+1] = 89交換後 : [j] = 89, [j+1] = 5
i = 2, j = 1 : [j] = 5, [j+1] = 41交換後 : [j] = 41, [j+1] = 5
i = 2, j = 2 : [j] = 5, [j+1] = 17交換後 : [j] = 17, [j+1] = 5
[89, 41, 17, 5, 3, 2]

i = 3, j = 0 : [j] = 89, [j+1] = 41不交換

i = 3, j = 1 : [j] = 41, [j+1] = 17不交換

[89, 41, 17, 5, 3, 2]

i = 4, j = 0 : [j] = 89, [j+1] = 41不交換

[89, 41, 17, 5, 3, 2]

排序後 : [89, 41, 17, 5, 3, 2]

# 3.循序搜尋 : 中獎者姓名 <sequential>
num = [256,731,943,389,142,645,829,945]
name = ["林小虎","王中森","邵木淼","李大同","陳子孔","鄭美麗","曾溫柔","錢來多"]
no = int(input("請輸入中獎者的編號 ："))
 
IsFound=False
for i in range(len(name)):  #逐一比對搜尋 
    if (num[i]==no):        #號碼相符 
        IsFound=True        #設旗標為 True
        break               #結束比對

if (IsFound==True):
    print("中獎者的姓名為 ：",name[i])
else:
    print("無此中獎號碼！")
print("共比對 %d次 " %(i+1))   

請輸入中獎者的編號 ：829
中獎者的姓名為 ： 曾溫柔
共比對 7次

# 4.二分搜尋 : 中獎者姓名 <binary>
num=[256,731,943,389,142,645,829,945,371,418]
name=["林小虎","王中森","邵木淼","李大同","陳子孔","鄭美麗","曾溫柔","錢來多","賈天良","吳水品"] 

n=len(num)-1 # 串列長度-1
IsFound=False
min=0
max=n
c=0 #計算比對次數 

for i in range(0,n): 
    for j in range(0,n-i):         
        if (num[j]>num[j+1]): # 由小到大排序
            num[j],num[j+1]=num[j+1],num[j]     # 兩數互換
            name[j],name[j+1]=name[j+1],name[j] # 姓名互換
 
no = int(input("請輸入中獎者的編號："))

while(min<=max):
    mid=int((min+max)/2)
    c+=1  #比對次數加 1
    if (num[mid]==no):  #號碼相符 
        IsFound=True
        break

    if (num[mid]>no): #如果中間值大於輸入值 
       max=mid-1      #使用較小的一半區域繼續比對 
    else:             #如果中間值不大於輸入值 
       min=mid+1      #使用較大的一半區域繼續比對 
       
if (IsFound==True):
    print("中獎者的姓名為 ：",name[mid])
else:
    print("無此中獎號碼！")
print("共比對 ",c,"次")              

請輸入中獎者的編號：829
中獎者的姓名為 ： 曾溫柔
共比對 2 次

### {綜合演練}
<pre>
實作2 :
俊民將中獎號碼建立成串列num=[67,12,9,52,91,3]，
讓妹妹輸入三個號碼，再以循序搜尋方法檢查這三個號碼種有幾個中獎，
並顯示其結果。
<pre/>

<pre>
實作3:
下列名單為本期大樂透的中獎名單names=["David","Lily","Chiou","Bear","Shantel","Chynthia"]，讓使用者輸入一個姓名，輸入的字元大小寫不分，例如輸入 david、David、DAVID 都是同一人，請以二分搜尋法檢查該名單是否中獎，並顯示查詢結果。
<pre/>

names = ["David","Lily","Chiou","Bear","Shantel","Chynthia"] 
n = len(names)-1
for i in range(0,n) : 
    for j in range(0,n-i) :         
        if (names[j]>names[j+1]) : 
            names[j],names[j+1]=names[j+1],names[j] 
            
while True : 
    name = input("請輸入中獎者的名單(enter結束)：")
    if (name=="") :
        break
    
    IsFound=False
    min=0
    max=n
    while(min<=max) :
        mid=int((min+max)/2)
        if (names[mid].upper()==name.upper()) :
            IsFound = True
            break
        if (names[mid].upper()>name.upper()) :
            max=mid-1      
        else:             
            min=mid+1   

    if (IsFound==True) :
        print("恭喜您，",name,"中獎了!")
    else :
        print("可惜，",name,"未中獎!")

請輸入中獎者的名單(enter結束)：lily
恭喜您， lily 中獎了!
請輸入中獎者的名單(enter結束)：amy
可惜， amy 未中獎!
請輸入中獎者的名單(enter結束)：shantel
恭喜您， shantel 中獎了!
請輸入中獎者的名單(enter結束)：

## 【afterclass practice】

1. OMP feedback