# wk14_演算法_排序與搜尋_陳姿頴
8.3 搜尋
1. 循序搜尋
2. 二分搜尋
## 【inclass practice】
```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
```python
def switch(i) :
datas[i], datas[i+1] = datas[i+1], datas[i]
datas = [31,5,12,1]
print("排序前", datas)
n = len(datas)
#for i in range(0, n-1):
for i in range(n-1): #跑(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)
```
排序前 [31, 5, 12, 1]
i = 0, j= 0 : [j]=31,[j+1]=5 不交換
i = 0, j= 1 : [j]=5,[j+1]=12 交換後 : [j]=12, [j+1]=5
i = 0, j= 2 : [j]=5,[j+1]=1 不交換
[31, 12, 5, 1]
i = 1, j= 0 : [j]=31,[j+1]=12 不交換
i = 1, j= 1 : [j]=12,[j+1]=5 不交換
[31, 12, 5, 1]
i = 2, j= 0 : [j]=31,[j+1]=12 不交換
[31, 12, 5, 1]
排序後 [31, 12, 5, 1]
```python
# 中獎者姓名(循序搜尋) <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))
```
請輸入中獎者的編號：16
無此中獎號碼！
共比對 8次
實作3:
下列名單為本期大樂透的中獎名單name=['David','Lily','Chiou','Bear','Shantel','Chynthia']，
讓使用者輸入一個姓名，輸入的字元大小寫不分，
例如輸入 david、David、DAVID都是同一人，
請以二分搜尋法檢查該名單是否中獎，
並顯示查詢結果。
```python
# 二分搜尋法
names=["David","Lily","Chiou","Bear","Shantel","Cynthia"]
n=len(names)-1 # 串列長度-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
# 目標串列: 0~n
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結束)：david
恭喜您， david 中獎了!
請輸入中獎者的名單(Enter結束)：
```python
# 期末專題參考
! pip install wikipedia
```
Requirement already satisfied: wikipedia in c:\users\user\anaconda3\lib\site-packages (1.4.0)
Requirement already satisfied: beautifulsoup4 in c:\users\user\anaconda3\lib\site-packages (from wikipedia) (4.12.2)
Requirement already satisfied: requests<3.0.0,>=2.0.0 in c:\users\user\anaconda3\lib\site-packages (from wikipedia) (2.31.0)
Requirement already satisfied: charset-normalizer<4,>=2 in c:\users\user\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:\users\user\anaconda3\lib\site-packages (from requests<3.0.0,>=2.0.0->wikipedia) (3.4)
Requirement already satisfied: urllib3<3,>=1.21.1 in c:\users\user\anaconda3\lib\site-packages (from requests<3.0.0,>=2.0.0->wikipedia) (1.26.16)
Requirement already satisfied: certifi>=2017.4.17 in c:\users\user\anaconda3\lib\site-packages (from requests<3.0.0,>=2.0.0->wikipedia) (2023.7.22)
Requirement already satisfied: soupsieve>1.2 in c:\users\user\anaconda3\lib\site-packages (from beautifulsoup4->wikipedia) (2.4)
```python
import wikipedia as wiki
```
```python
# 設定語言
wiki.set_lang("zh")
searchtarget = input('請輸入要搜尋的項目:')
searchResult = wiki.search(searchtarget)
print(f'搜尋結果=>{searchResult}')
```
請輸入要搜尋的項目:星座
搜尋結果=>['星座', '星座恒星列表', '已廢棄星座', '洛克希德星座', '星座面積列表', '星座列表', '星座愛情牡羊女', '星座號航空母艦', '星座愛情獅子女', '星座号对战复仇号']
```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-星座號航空母艦
8-星座愛情獅子女
9-星座号对战复仇号
※請選擇想要的結果:9
[星座号对战复仇号]摘要=>星座号对战复仇号（英語：USS Constellation vs La Vengeance）又称“1800年2月1日战斗”（Action of 1 February 1800），是美法短暂冲突期间发生的单舰海战，战斗起因是美国海军星座号巡防舰试图俘获法国海军复仇号巡防舰。交战双方伤亡惨重，舰只严重损毁。法方在战斗中两次降旗投降，但还是在对手主桅杆倒塌后顺利逃脱。
1798年，因法国扣押美国商船，双方不宣而战。为阻止法方攻势，托马斯·特鲁克斯顿海军准将受命率领美国分舰队赶赴小安的列斯群岛。发现法国正规海军后，特鲁克斯顿亲自带领旗舰星座号前往瓜德罗普交战。1800年2月1日，星座号在逼近法属殖民地期间同弗朗索瓦·皮托指挥的复仇号激烈交战，双方伤亡都很惨重，舰只严重受损。星座号重创之余开往牙买加维修，回国时得到英雄凯旋般的欢迎。
```python
import os, pathlib
```
```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')
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'\n'
reportText +=f'##參考連結\n'
references = page.references
for reference in references:
reportText += f'-{reference}\n'
f.write(reportText)
f.close()
```
##分類/n['1800年军事冲突', '1800年法国', '1800年美国', '典范条目', '含有法語的條目', '含有英語的條目', '法國海戰', '美国海战', '美法短暂冲突海战']
##摘要/n星座号对战复仇号（英語：USS Constellation vs La Vengeance）又称“1800年2月1日战斗”（Action of 1 February 1800），是美法短暂冲突期间发生的单舰海战，战斗起因是美国海军星座号巡防舰试图俘获法国海军复仇号巡防舰。交战双方伤亡惨重，舰只严重损毁。法方在战斗中两次降旗投降，但还是在对手主桅杆倒塌后顺利逃脱。
1798年，因法国扣押美国商船，双方不宣而战。为阻止法方攻势，托马斯·特鲁克斯顿海军准将受命率领美国分舰队赶赴小安的列斯群岛。发现法国正规海军后，特鲁克斯顿亲自带领旗舰星座号前往瓜德罗普交战。1800年2月1日，星座号在逼近法属殖民地期间同弗朗索瓦·皮托指挥的复仇号激烈交战，双方伤亡都很惨重，舰只严重受损。星座号重创之余开往牙买加维修，回国时得到英雄凯旋般的欢迎。
##網址/nhttps://zh.wikipedia.org/wiki/%E6%98%9F%E5%BA%A7%E5%8F%B7%E5%AF%B9%E6%88%98%E5%A4%8D%E4%BB%87%E5%8F%B7
##內容/n星座号对战复仇号（英語：USS Constellation vs La Vengeance）又称“1800年2月1日战斗”（Action of 1 February 1800），是美法短暂冲突期间发生的单舰海战，战斗起因是美国海军星座号巡防舰试图俘获法国海军复仇号巡防舰。交战双方伤亡惨重，舰只严重损毁。法方在战斗中两次降旗投降，但还是在对手主桅杆倒塌后顺利逃脱。
1798年，因法国扣押美国商船，双方不宣而战。为阻止法方攻势，托马斯·特鲁克斯顿海军准将受命率领美国分舰队赶赴小安的列斯群岛。发现法国正规海军后，特鲁克斯顿亲自带领旗舰星座号前往瓜德罗普交战。1800年2月1日，星座号在逼近法属殖民地期间同弗朗索瓦·皮托指挥的复仇号激烈交战，双方伤亡都很惨重，舰只严重受损。星座号重创之余开往牙买加维修，回国时得到英雄凯旋般的欢迎。
== 背景 ==
1800年，美法短暂冲突如火如荼。为制止法国在加勒比地区袭击美国商船，美国海军派出四个分舰队在当地巡逻，其中负责小安的列斯群岛海域的分舰队由托马斯·特鲁克斯顿（Thomas Truxton）海军准将统领。1800年1月19日，特鲁克斯顿乘旗舰星座号（USS Constellation）巡防舰抵达圣基茨岛，整个分舰队包含四艘巡防舰，三艘双桅纵帆船和一艘全帆装战船。除多起私掠行动外，特鲁克斯顿负责海域的法国海军正规军只有弗朗索瓦·皮托（François Pitot）带领的复仇号（HMS Vengeance）巡防舰和路易·塞内斯（Louis Senes）统领的摇篮号（La Berceau）护卫舰，两舰均因护送新任法国殖民地官员而在1799年12月10日到达瓜德罗普。特鲁克斯顿命令所有舰只散开后独立巡航，然后在1800年1月30日乘星座号前往瓜德罗普，准备同法国两艘正规舰只交战；当天皮托带领复仇号离开瓜德罗普首府巴斯特尔，打算返回法国。
星座号排水量1265吨，装有38门炮，美国海军将其正式列为36炮巡防舰。船上原本都是24磅长炮，但在俘获法军叛乱者号（L'Insurgente）巡防舰的战斗中效率不足，故改装28门18磅炮和十门24磅卡隆炮（Carronade）。特鲁克斯顿及众船员都是经验丰富的老兵，对交战准备充分。相比之下，复仇号巡防舰虽然火力更强，配有八门42磅卡隆炮，28门18磅炮和16门12磅加农炮，而且共计380名船员在需要登船作战时也比只有310人的星座号优势显著，但船上载有大量硬币，还有36名美国战俘，包括两位将军在内的80名乘客，所以皮托只想尽可能避免交战。
== 交战 ==
1800年2月1日早上7点，星座号船员发现距巴斯特尔两里格海域有一艘战船，看上去似乎是挂上英国旗帜的54炮巡防舰。为联络对方，星座号挂出英国军舰旗。7点45分，皮托已经看到星座号，以为身后追踪的是火力更强的55炮军舰。为避免冲突，他没有按原计划北上，而是改为顺风航行。为加速还打开辅助帆，获得更多风力。此举导致特鲁克斯顿明白前方是法国战舰，所以下令追赶并准备战斗。8点，星座号已用美国旗帜换下英国舰旗，逼近后还用喇叭筒喊话，要求复仇号投降。法舰舰尾炮率先向星座号开火，战斗正式打响。为抵消美方速度优势，复仇者转向东南以求获得有利风向。皮托操纵船只期间，法舰侧炮开火命中星座号风帆撑架。美方将船开到敌舰上风位置后还击。凭借风向优势，特鲁克斯顿下令船侧舰炮近距离向复仇号船体猛烈开火。两船你追我赶，持续交战两个半小时，其间特鲁克斯顿试图把船移到扫射火力位置，但没有成功。法方主要瞄准索具和船帆开炮，一度打掉星座号前帆，美方补上后才恢复机动。22点45分，两艘巡防舰的距离已经很短，复仇号准备登船作战，但被美方船侧发射的葡萄弹和美国海军陆战队的滑膛枪及手榴弹压制。双舰接下来拉开距离，使用射程更远的球型弹对决，战斗持续到2月2日凌晨两点，复仇号第二次降旗投降。此前皮托就曾投降一次，但美方因天黑没有看到。特鲁克斯顿命令星座号靠近法舰至不足23米位置，准备收取战利品。然而，美舰的主桅杆在凌晨三点倒塌，多名船员摔死。皮托抓住这难得的机会，在黑暗中顺利逃脱。
== 影响 ==
交战双方伤亡惨重，两舰损伤严重，特鲁克斯顿和皮托都一度以为敌舰已被击沉。复仇号大部分船帆和索具被炮火击落，只有下前桅、下后桅和船首斜桅基本正常。皮托改道库拉索，为防止沉船只能在岛上搁浅。法方具体伤亡人数尚具争议：官方公布数据是28人死亡，40人受伤，库拉索的统计声称复仇号有160人死亡。皮托抵达库拉索后无法从荷兰殖民地官员手中获得修补船只需要的物品，此后几个月都不能出海，直到下半年法国入侵库拉索才为他带来足够军需。修好复仇号后，皮托拒绝参战，离开库拉索前往瓜德罗普。星座号同样受到重创，15人死亡，25人受伤，其中11人伤重不治。美舰开到牙买加皇家港整修，但因海洋建材短缺无法完工。星座号一周后离开牙买加，此时仅有主桅杆已更换。将14艘商船护送回美国后，特普克斯顿把千疮百孔的巡防舰开到汉普顿锚地修理，他本人直到返回美国后才得知复仇号没有击沉。特普克斯顿因此次作战获得普遍认可，赢得英雄般的赞誉，美国政府授予他“国会金质奖章”，奖章背面就刻有这场海战的情景。
== 脚注 ==
== 来源 ==
##圖片
##參考連結
-https://books.google.com.ph/books?id=4bFEAAAAIAAJ&redir_esc=y
-https://books.google.com.ph/books?id=x-U-AAAAYAAJ&pg=PA306&redir_esc=y
-https://books.google.com.ph/books?id=JBASAAAAYAAJ&pg=PA190&redir_esc=y
-https://books.google.com.ph/books?id=pf0WAQAAIAAJ&redir_esc=y
-https://books.google.com.ph/books?id=DVr1RI2GuOMC&pg=PA188&redir_esc=y
-https://archive.org/details/sixfrigatesepich00toll
-https://books.google.com.ph/books?id=rhIR5D5quFYC&redir_esc=y
-https://web.archive.org/web/20210309235559/https://books.google.com.ph/books?id=4bFEAAAAIAAJ&redir_esc=y
-https://web.archive.org/web/20210310001605/https://books.google.com.ph/books?id=x-U-AAAAYAAJ&pg=PA306&redir_esc=y
-https://web.archive.org/web/20210309233537/https://books.google.com.ph/books?id=JBASAAAAYAAJ&pg=PA190&redir_esc=y
-https://web.archive.org/web/20210307101216/https://books.google.com.ph/books?id=pf0WAQAAIAAJ&redir_esc=y
-https://web.archive.org/web/20210309233518/https://books.google.com.ph/books?id=DVr1RI2GuOMC&pg=PA188&redir_esc=y
-https://web.archive.org/web/20210310001629/https://books.google.com.ph/books?id=rhIR5D5quFYC&redir_esc=y
-https://www.worldcat.org/oclc/1202325
-https://www.worldcat.org/oclc/4765607
-https://www.worldcat.org/oclc/2622223
-https://www.worldcat.org/oclc/15162322
-https://www.worldcat.org/oclc/634744808
-https://www.worldcat.org/oclc/633333009
## 【afterclass practice】
1. 名詞解釋 : 排序、搜尋
- 排序: 以由小到大的氣泡排序為例，比較相鄰的元素，如果第一個比第二個大，就將兩元素進行交換，對每一對相鄰元素重複相同步驟，直到沒有任何一隊數字需要比較。
- 搜尋: 循序搜尋不用排序，從串列中第一個串列元素開始搜尋，如果找到目標，結束搜尋，如果沒有找到目標，繼續搜尋下一個串列元素，直到串列元素全部搜尋完為止。
## 【selfpractice】
### {綜合演練}
實作2 :
俊民將中獎號碼建立成串列num=[67,12,9,52,91,3]，
讓妹妹輸入三個號碼，再以循序搜尋方法檢查這三個號碼種有幾個中獎，
並顯示其結果。
```python
num = [67, 12, 9, 52, 91, 3]
input_numbers = []
for i in range(3):
number = int(input(f"請輸入第{i+1}個號碼: "))
input_numbers.append(number)
winning_count = 0
for number in input_numbers:
if number in num:
winning_count += 1
print(f"妹妹輸入的號碼為：{input_numbers}")
print(f"中獎數量為：{winning_count} 個")
```
請輸入第1個號碼: 1
請輸入第2個號碼: 2
請輸入第3個號碼: 4
妹妹輸入的號碼為：[1, 2, 4]
中獎數量為：0 個
```python
# 二分搜尋: 中獎者姓名 \<binary>
num = [142, 256, 389, 645, 731, 829, 943, 945] # Sorted list
name = ["林小虎", "王中森", "邵木淼", "李大同", "陳子孔", "鄭美麗", "曾溫柔", "錢來多"]
no = int(input("請輸入中獎者的編號: "))
IsFound = False
low = 0
high = len(num) - 1
while low <= high:
mid = (low + high) // 2
if num[mid] == no:
IsFound = True
break
elif num[mid] < no:
low = mid + 1
else:
high = mid - 1
if IsFound:
print("中獎者的姓名為：", name[mid])
print("共比對 %d 次" % (mid + 1))
else:
print("無此中獎號碼！")
print("共比對 %d 次" % (mid + 1))
```
請輸入中獎者的編號: 123
無此中獎號碼！
共比對 1 次
Sign in with Wallet
Connect another wallet