---
# System prepended metadata

title: wk14_1207
tags: [Python]

---

## 【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'![]({img})\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://upload.wikimedia.org/wikipedia/commons/8/87/Lorenzo_di_Bonaventura_by_Gage_Skidmore.jpg)
## 參考連結
- 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
    
