## 【wk14_1207】演算法_排序與搜尋
## 【ch08_演算法_排序與搜尋】
## 【inclass practice】
8.3 搜尋
- 循序搜尋
- 二分搜尋
```python
# 由小排到大排序 <bubble>
# 補上星期
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):
#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]
{綜合演練}
實作2 :
俊民將中獎號碼建立成串列num=[67,12,9,52,91,3]，讓妹妹輸入三個號碼，再以循序搜尋方法檢查這三個號碼種有幾個中獎，並顯示其結果。
```python
# 循序搜尋
num=[67,12,9,52,91,3]
datas=[]
for i in range(0,3):
no = int(input("請輸入第 " + str(i+1) + " 個號碼："))
# 將號碼轉為數值後加入 datas 串列中
datas.append(no)
n=0
for i in range(0,3):
for j in range(len(num)): #逐一比對搜尋
if (num[j]==datas[i]): #號碼相符
n+=1
break #結束比對
if (n>0):
print("恭喜您，中了",n,"個號碼!")
else:
print("可惜，您未中獎！")
```
請輸入第 1 個號碼：12
請輸入第 2 個號碼：16
請輸入第 3 個號碼：44
恭喜您，中了 1 個號碼!
{綜合演練}
實作3:
下列名單為本期大樂透的中獎名單name=['David','Lily','Chiou','Bear','Shantel','Chynthia']，讓使用者輸入一個姓名，輸入的字元大小寫不分，例如輸入 david、David、DAVID都是同一人，請以
1)循序法
2)二分搜尋法
檢查該名單是否中獎，並顯示查詢結果。
```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
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結束)：alice
可惜， alice 未中獎！
請輸入中獎者的名單(Enter結束)：
```python
# 期末專題參考
! pip install wikipedia
```
Defaulting to user installation because normal site-packages is not writeable
Requirement already satisfied: wikipedia in c:\users\user\appdata\roaming\python\python310\site-packages (1.4.0)
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: 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: 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: 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: soupsieve>1.2 in c:\programdata\anaconda3\lib\site-packages (from beautifulsoup4->wikipedia) (2.3.2.post1)
```python
import wikipedia as wiki
```
```python
# 設定語言
wiki.set_lang("zh")
searchtarget = input('請輸入要搜尋的項目: ')
searchResult = wiki.search(searchtarget)
print(f'搜尋結果 => {searchResult}')
```
請輸入要搜尋的項目: cgu
搜尋結果 => ['CGU', '孔波斯特拉大學集團', '洛倫佐·迪·波納文圖拉', '克萊蒙研究大學', '鹼性燃料電池', '無義突變', '錯義突變', '精氨酸', '凯斯纽荷兰环球', '米库喵']
```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 - CGU
1 - 孔波斯特拉大學集團
2 - 洛倫佐·迪·波納文圖拉
3 - 克萊蒙研究大學
4 - 鹼性燃料電池
5 - 無義突變
6 - 錯義突變
7 - 精氨酸
8 - 凯斯纽荷兰环球
9 - 米库喵
請選擇想要的結果: 2
[洛倫佐·迪·波納文圖拉] 摘要 => 洛倫佐·迪·波納文圖拉（英語：Lorenzo di Bonaventura，義大利語發音：[loˈrɛntso di ˌbɔnavenˈtuːra]，1957年1月13日—）是一名美國男製片人，同時也是迪·波納文圖拉影業的創始人。他以製作《变形金刚》系列電影（2007年至今）而聞名。
```python
import wikipedia as wiki
# 設定語言
wiki.set_lang("zh")
search_target = input('請輸入要搜尋的項目: ')
# 透過搜尋獲取相關條目的標題
search_result = wiki.search(search_target)
if not search_result:
print("未找到相關條目。")
else:
# 顯示搜尋結果供使用者選擇
for i, result in enumerate(search_result):
print(f'{i} - {result}')
index = int(input('請選擇想要的結果: '))
# 確保使用者選擇的索引在合法範圍內
if 0 <= index < len(search_result):
target = search_result[index]
# 透過標題獲取條目的詳細內容
try:
page = wiki.page(target)
print(f'\n搜尋結果：{page.title}\n')
print(page.summary)
except wiki.exceptions.DisambiguationError as e:
print(f"消歧義頁面，可能的選項: {e.options}")
except wiki.exceptions.PageError as e:
print(f"找不到條目：{e}")
else:
print("輸入的索引超出範圍。")
```
請輸入要搜尋的項目: cgu
0 - CGU
1 - 孔波斯特拉大學集團
2 - 洛倫佐·迪·波納文圖拉
3 - 克萊蒙研究大學
4 - 鹼性燃料電池
5 - 無義突變
6 - 錯義突變
7 - 精氨酸
8 - 凯斯纽荷兰环球
9 - 米库喵
請選擇想要的結果: 2
搜尋結果：洛倫佐·迪·波納文圖拉
洛倫佐·迪·波納文圖拉（英語：Lorenzo di Bonaventura，義大利語發音：[loˈrɛntso di ˌbɔnavenˈtuːra]，1957年1月13日—）是一名美國男製片人，同時也是迪·波納文圖拉影業的創始人。他以製作《变形金刚》系列電影（2007年至今）而聞名。
```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{categories}\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()
```
# 洛倫佐·迪·波納文圖拉
## 分類
['1957年出生', 'CS1美国英语来源 (en-us)', 'CS1英语来源 (en)', '包含BIBSYS标识符的维基百科条目', '包含BNE标识符的维基百科条目', '包含GND标识符的维基百科条目', '包含ISNI标识符的维基百科条目', '包含J9U标识符的维基百科条目', '包含LCCN标识符的维基百科条目', '包含MusicBrainz标识符的维基百科条目', '包含NLP标识符的维基百科条目', '包含NTA标识符的维基百科条目', '包含VIAF标识符的维基百科条目', '含有hCards的条目', '含有英語的條目', '哈佛大學校友', '在世人物', '宾夕法尼亚大学沃顿商学院校友', '本地相关图片与维基数据相同', '紐約州人', '美國電影監製', '義大利裔美國人']
## 摘要
['1957年出生', 'CS1美国英语来源 (en-us)', 'CS1英语来源 (en)', '包含BIBSYS标识符的维基百科条目', '包含BNE标识符的维基百科条目', '包含GND标识符的维基百科条目', '包含ISNI标识符的维基百科条目', '包含J9U标识符的维基百科条目', '包含LCCN标识符的维基百科条目', '包含MusicBrainz标识符的维基百科条目', '包含NLP标识符的维基百科条目', '包含NTA标识符的维基百科条目', '包含VIAF标识符的维基百科条目', '含有hCards的条目', '含有英語的條目', '哈佛大學校友', '在世人物', '宾夕法尼亚大学沃顿商学院校友', '本地相关图片与维基数据相同', '紐約州人', '美國電影監製', '義大利裔美國人']
## 網址
https://zh.wikipedia.org/wiki/%E6%B4%9B%E5%80%AB%E4%BD%90%C2%B7%E8%BF%AA%C2%B7%E6%B3%A2%E7%B4%8D%E6%96%87%E5%9C%96%E6%8B%89
## 內容
洛倫佐·迪·波納文圖拉（英語：Lorenzo di Bonaventura，義大利語發音：[loˈrɛntso di ˌbɔnavenˈtuːra]，1957年1月13日—）是一名美國男製片人，同時也是迪·波納文圖拉影業的創始人。他以製作《变形金刚》系列電影（2007年至今）而聞名。
== 早期生活 ==
洛倫佐·迪·波納文圖拉的父親馬里歐·迪·波納文圖拉（Mario di Bonaventura）是一位交響樂指揮家，而叔叔安東尼·迪·波納文圖拉則是一位鋼琴演奏家。迪·波納文圖拉畢業於宾夕法尼亚大学與哈佛大學。他後來獲得了宾夕法尼亚大学沃顿商学院的MBA學位。
== 個人生活 ==
迪·波納文圖拉為Represent.Us的創意委員會主席，這是一個非黨派、非營利的反腐敗組織。自2015年以來，他一直任職於克萊蒙特研究生大學董事會（Claremont Graduate University Board of Trustees）。
他於2017年和妻子金柏莉·迪·波納文圖拉（Kimberly di Bonaventura）離婚，並於隔年和布拉克·迪·波納文圖拉（Brooke di Bonaventura）結婚。
== 參考資料 ==
== 外部連結 ==
洛倫佐·迪·波納文圖拉在互联网电影资料库（IMDb）上的資料（英文）
## 圖片
## 參考連結
- https://zff.com/en/festival-info/news/2016/1450/career-achievement-award-to-lorenzo-di-bonaventura/
- http://www.bach-cantatas.com/Lib/Bonaventura-Mario.htm
- https://variety.com/2010/film/news/di-bonaventura-on-a-bonny-venture-1118025192/
- https://represent.us/about/
- https://www.cgu.edu/about/board-of-trustees/lorenzo-di-bonaventura/
- https://www.worldcat.org/identities/containsVIAFID/51135321
- https://authority.bibsys.no/authority/rest/authorities/html/11063023
- http://catalogo.bne.es/uhtbin/authoritybrowse.cgi?action=display&authority_id=XX1785285
- https://d-nb.info/gnd/116336083X
- http://isni.org/isni/000000006639324X
- http://id.loc.gov/authorities/names/n2007020371
- https://musicbrainz.org/artist/7e560f03-601f-4efe-bbe0-7df1f6511c39
- https://viaf.org/viaf/51135321
- https://www.wikidata.org/wiki/Q636664
- https://commons.wikimedia.org/wiki/Category:Lorenzo_di_Bonaventura?uselang=zh
- https://web.archive.org/web/20190228221500/http://www.bach-cantatas.com/Lib/Bonaventura-Mario.htm
- https://web.archive.org/web/20161023054916/https://represent.us/about/
- http://data.bibliotheken.nl/id/thes/p375798897
- https://web.archive.org/web/20190909043957/https://zff.com/en/festival-info/news/2016/1450/career-achievement-award-to-lorenzo-di-bonaventura/
- https://web.archive.org/web/20200826000846/https://variety.com/2010/film/news/di-bonaventura-on-a-bonny-venture-1118025192/
- https://web.archive.org/web/20201124014606/https://www.cgu.edu/about/board-of-trustees/lorenzo-di-bonaventura/
- https://www.imdb.com/name/nm0225146/
- http://uli.nli.org.il/F/?func=find-b&local_base=NLX10&find_code=UID&request=987007404959505171
- http://mak.bn.org.pl/cgi-bin/KHW/makwww.exe?BM=01&IM=04&NU=01&WI=a0000002259399
## 【afterclass practice】
名詞解釋 : 排序、搜尋
#### 排序（Sorting）
- 是指將一組元素按照特定的規則或順序重新排列的過程
- 最常見的是快速排序（Quicksort）、合併排序（Mergesort）、冒泡排序（Bubblesort）等
- Python提供內建的sorted()函數，該函數可以對列表（list）或其他可迭代對象進行排序。此外，列表的sort()方法也可以用來原地排序
```python
# sorted()
numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_numbers = sorted(numbers)
print(sorted_numbers)
```
[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
#### 搜尋（Searching）
- 指在一個資料集合中查找特定元素的過程
- 常見的搜尋算法包括線性搜尋（Linear Search）和二分搜尋（Binary Search）
- 線性搜尋:從頭到尾逐一檢查每個元素，直到找到目標元素或檢查完整個集合
- 二分搜尋:要求資料集合是已經排序的，它通過反覆將查找範圍分半，縮小搜尋範圍，直到找到目標元素
- 資料集合已經排序，可以考慮使用二分搜尋，它通常比線性搜尋更有效率，尤其當資料集合較大時
```python
def linear_search(lst, target):
for i, item in enumerate(lst):
if item == target:
return i
return -1 # 表示未找到目標元素
numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
target_index = linear_search(numbers, 4)
print(target_index)
```
2
## 【self practice】
```python
# 循序搜尋
def linear_search(lst, target):
"""
在列表中使用循序搜尋尋找目標元素的索引。
Parameters:
- lst: 要搜尋的列表
- target: 要尋找的目標元素
Returns:
- 如果找到目標元素，返回目標元素的索引；如果未找到，返回 -1。
"""
for i, item in enumerate(lst):
if item == target:
return i
return -1
numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
target_linear = 4
result_linear = linear_search(numbers, target_linear)
print(f"循序搜尋：目標 {target_linear} 在索引 {result_linear}" if result_linear != -1 else "循序搜尋：目標未找到")
```
循序搜尋：目標 4 在索引 2
```python
# 二分搜尋
# 假設列表已經排序
def binary_search(lst, target):
"""
在已排序的列表中使用二分搜尋尋找目標元素的索引。
Parameters:
- lst: 已排序的列表
- target: 要尋找的目標元素
Returns:
- 如果找到目標元素，返回目標元素的索引；如果未找到，返回 -1。
"""
low, high = 0, len(lst) - 1
while low <= high:
mid = (low + high) // 2
mid_value = lst[mid]
if mid_value == target:
return mid
elif mid_value < target:
low = mid + 1
else:
high = mid - 1
return -1
sorted_numbers = sorted(numbers)
target_binary = 4
result_binary = binary_search(sorted_numbers, target_binary)
print(f"二分搜尋：目標 {target_binary} 在排序後的列表中的索引 {result_binary}" if result_binary != -1 else "二分搜尋：目標未找到")
```
二分搜尋：目標 4 在排序後的列表中的索引 5
Sign in with Wallet
Connect another wallet