---
# System prepended metadata

title: wk14_1207_ch08_演算法_排序與搜尋

---

## wk14_1207_ch08_演算法_排序與搜尋

8.3 搜尋

1. 循序搜尋
2. 二分搜尋

## 【inclass practice】

實作2 :

俊民將中獎號碼建立成串列num=[67,12,9,52,91,3]，
讓妹妹輸入三個號碼，再以循序搜尋方法檢查這三個號碼種有幾個中獎，
並顯示其結果。


```python
#2.追蹤泡沫排序法的過程 <bubble_debuge>
def disp_data(): # 顯示串列的自訂程序
    for item in datas:
        print(item,end=" ")
    print()        

# 主程式
datas=[3,5,2,1]  
print("排序前：",end=" ")
disp_data() # 顯示排序前串列
n=len(datas)-1 # 串列長度-1

for i in range(0,n): 
    for j in range(0,n-i):      
        print("i=%d j=%d" %(i,j))
        if (datas[j]>datas[j+1]): # 由大到小排序
            print("%d,%d 互換後" %(datas[j],datas[j+1]) ,end="：")
            datas[j],datas[j+1]=datas[j+1],datas[j] # 兩數互換
        print(datas)

print("排序後：",end=" ")  
disp_data()  # 顯示排序後串列 
```

    排序前： 3 5 2 1 
    i=0 j=0
    [3, 5, 2, 1]
    i=0 j=1
    5,2 互換後：[3, 2, 5, 1]
    i=0 j=2
    5,1 互換後：[3, 2, 1, 5]
    i=1 j=0
    3,2 互換後：[2, 3, 1, 5]
    i=1 j=1
    3,1 互換後：[2, 1, 3, 5]
    i=2 j=0
    2,1 互換後：[1, 2, 3, 5]
    排序後： 1 2 3 5 
    

實作3:

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


```python
# 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次 
    


```python
#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 ," 次")      
```

    請輸入中獎者的編號：142
    中獎者的姓名為： 陳子孔
    共比對  3  次
    


```python
!pip install wikipedia
```

    Defaulting to user installation because normal site-packages is not writeable
    Collecting wikipedia
      Downloading wikipedia-1.4.0.tar.gz (27 kB)
      Preparing metadata (setup.py): started
      Preparing metadata (setup.py): finished with status 'done'
    Requirement already satisfied: beautifulsoup4 in c:\programdata\anaconda3\lib\site-packages (from wikipedia) (4.11.1)
    Requirement already satisfied: requests<3.0.0,>=2.0.0 in c:\programdata\anaconda3\lib\site-packages (from wikipedia) (2.28.1)
    Requirement already satisfied: urllib3<1.27,>=1.21.1 in c:\programdata\anaconda3\lib\site-packages (from requests<3.0.0,>=2.0.0->wikipedia) (1.26.14)
    Requirement already satisfied: certifi>=2017.4.17 in c:\programdata\anaconda3\lib\site-packages (from requests<3.0.0,>=2.0.0->wikipedia) (2023.5.7)
    Requirement already satisfied: charset-normalizer<3,>=2 in c:\programdata\anaconda3\lib\site-packages (from requests<3.0.0,>=2.0.0->wikipedia) (2.0.4)
    Requirement already satisfied: idna<4,>=2.5 in c:\programdata\anaconda3\lib\site-packages (from requests<3.0.0,>=2.0.0->wikipedia) (3.4)
    Requirement already satisfied: soupsieve>1.2 in c:\programdata\anaconda3\lib\site-packages (from beautifulsoup4->wikipedia) (2.3.2.post1)
    Building wheels for collected packages: wikipedia
      Building wheel for wikipedia (setup.py): started
      Building wheel for wikipedia (setup.py): finished with status 'done'
      Created wheel for wikipedia: filename=wikipedia-1.4.0-py3-none-any.whl size=11707 sha256=982b581dca073b704dda15d0d1a748a6695a588bb3ebb2af77d4e23764edc19d
      Stored in directory: c:\users\user\appdata\local\pip\cache\wheels\b2\7f\26\524faff9145e274da278dc97d63ab0bfde1f791ecf101a9c95
    Successfully built wikipedia
    Installing collected packages: wikipedia
    Successfully installed wikipedia-1.4.0
    


```python
import wikipedia as wiki
```


```python
#設定語言
wiki.set_lang("zh")

searchtarget = input("請輸入要搜尋的項目: ")

searchResult = wiki.search(searchtarget)
print(f"搜尋結果 => {searchResult}")
```

    請輸入要搜尋的項目: 長庚
    搜尋結果 => ['長庚', '長庚醫療財團法人', '長庚科技大學', '長庚大學', '林口長庚紀念醫院', '李長庚 (明朝)', '李長庚', '李長庚 (1752年)', '長庚 (清朝同知)', '程长庚']
    


```python
que= " "
for i in range(len(searchResult)):
    que += f"{i} - {searchResult[i]}\n"

index = int(input(f"{que}#請選擇想要的結果: "))
target = searchResult[index]

summary = wiki.summary(target)
print(f"[{target}]摘要 => {summary}")
```

     0 - 長庚
    1 - 長庚醫療財團法人
    2 - 長庚科技大學
    3 - 長庚大學
    4 - 林口長庚紀念醫院
    5 - 李長庚 (明朝)
    6 - 李長庚
    7 - 李長庚 (1752年)
    8 - 長庚 (清朝同知)
    9 - 程长庚
    #請選擇想要的結果: 3
    [長庚大學]摘要 => 長庚大學，是位於臺灣桃園市龜山區的私立大學，前身長庚醫學院，由台塑企業創辦人王永慶於1987年設立。1997年8月由長庚醫學暨工程學院改制長庚大學。
    


```python
import os
```


```python
page = wiki.page(target)

reportText=" "

title = page.title

#如果檔案不存在，創建一個
if not os.path.isfile(f"./{title}.md"):
    with open(f"./{title}.md","w")as f: pass

f = open(f"./{title}.md","w", encoding="utf-8")
reportText += f"#{title}\n"

categories = page.categories
reportText += f"## 分類\n{categories}\n"

reportText += f"## 摘要\n{summary}\n"

url = page.url
reportText += f"## 網址\n{url}\n"

content = page.content
reportText += f"## 內容\n{content}\n"

reportText += f"## 圖片\n"
images = page.images
for img in images:
    if not img.endswith(".svg"):
        reportText += f"![]({img})\n"
        
reportText += f"## 參考連結\n"
references = page.references
for reference in references:
    reportText += f"- {reference}\n"

f.write(reportText)
f.close()
```