二元搜尋演算法是一種高效的搜尋方法，適用於已排序的資料集。其核心概念是利用資料集的有序性，每次比較中間元素與目標值，逐步縮小搜尋範圍，直到找到目標值或搜尋範圍為空。這種分治策略使得二元搜尋的時間複雜度為 O(log n)，相較於線性搜尋的 O(n) 效率更高，尤其在處理大規模資料時優勢顯著。在實際應用中，二元搜尋常被用於資料函式庫查詢、搜尋引擎和各種需要快速查詢特定元素的場景。理解並掌握二元搜尋演算法對於提升程式設計師的演算法思維和程式碼效率至關重要。
重構：讓程式碼更易讀、易維護
當你的程式完成時，不要立即離開。考慮重新設計它——只要沒有即將到來的截止日期。重新設計的目的不是最佳化，而是讓已經可以運作的程式碼更容易被理解、除錯、修改以及與其他程式碼整合，這種做法很常見，因此有了一個專門的名稱：重構。
重構意味著重新考慮變數和函式的名稱，將多工函式分解為單任務函式，應用逐步細化的原則，重新考慮資料結構的選擇，考慮內聚與耦合，並重寫程式碼以使其更清晰、更有效率。
為什麼需要重構？
曾經，我寫了一個簡單的函式，它接收一個字串和一個布林變數。我的直覺告訴我，這個函式可能正在執行兩個不同的任務。事實上，這個布林變數只是告訴函式要按照字母順序還是按照頻率順序輸出字串中的字元。後來，我發現我需要這個函式也能按照字元在字串中出現的順序輸出。於是我想到，可以透過傳遞布林值True、False，或者讓接收引數預設為None來實作。
然而，這種做法並不好。因為布林變數竟然會導致三種不同的值，這讓人難以理解。程式設計師需要假設某些情況永遠不會發生，即使它們是可能的。最終，我決定傳遞一個整數給這個函式，期望它只會是0、1或2。如果傳入其他值，程式會顯示警告訊息，並預設為0，但不會丟擲異常——也就是說，不會終止程式。
為什麼要有預設值？
因為函式的使用者可能不在乎輸出的順序，或者不想費事傳遞引數，又或者不知道有哪些可用的選項。因此，這個函式變得更加強壯了。
練習：寫一個函式傳回目標元素在陣列中的第一個索引，如果找不到則傳回-1。
下面的程式碼展示了三種不同的實作方法：
方法1（糟糕的實作）
def indx(array, target):
if array == []:
return -1
n = 0
found = -1
length = len(array)
while n != length:
if array[n] == target:
found = n
break
n += 1
return found
方法1內容解密：
此實作方式使用了while迴圈來遍歷陣列，並且使用了多個變數來追蹤目前的索引和是否找到目標元素。這種實作方式相對冗長且不易閱讀。
方法2（重構後的實作）
def indx(array, target):
for n in range(len(array)):
if array[n] == target:
return n
return -1
方法2內容解密：
此實作方式使用了for迴圈來遍歷陣列，並且直接在找到目標元素時傳回其索引。這種實作方式比方法1更簡潔、更易讀。
方法3（使用內建函式的實作）
def indx(array, target):
try:
return array.index(target)
except:
return -1
方法3內容解密：
此實作方式使用了Python的內建函式index()來查詢目標元素的索引。如果找不到目標元素，則捕捉異常並傳回-1。這種實作方式最簡潔，也最易於理解。
重構的價值
這些例子說明瞭為什麼學生需要檢視其他學生的程式碼，或者至少檢視老師的程式碼。透過這種方式學習到的經驗會一直伴隨著學生。重構提供了設計經驗，這對下一個專案有幫助。如果從不重新設計，就會停留在新手水平。
有時，函式A呼叫函式B。後來，我們有了函式A呼叫函式C，並使用函式B的內容。那麼，函式C應該呼叫函式B，而不是函式A。但是，如果我們這樣重新設計，那麼以後可能會丟棄函式C，然後不得不回溯。所以，在一段時間內，我們會忍受低效率的設計。只有當程式完成，或者即將失控時，我們才會考慮重新設計。
我認為，不太可能——至少效率不高——在一開始就完成一個設計良好的程式。太多的事情會在過程中改變。有些問題非常困難，以至於在看到程式當機之前，你不太可能理解任務的困難之處，或者如何正確地解決它。
重構：軟體開發的必經之路
軟體開發的過程並非一蹴而就，而是需要經過不斷的重構和改進。許多程式設計師在初學階段往往忽略了重構的重要性，他們認為只要程式能夠執行就算完成任務，但實際上，這只是開發的第一步。
重構的必要性
正如 David Parnas 和 Paul Clements 所說，「軟體設計師從需求陳述中以理性、無錯誤的方式推匯出設計的圖景是相當不現實的。從來沒有任何系統是以這種方式開發出來的，將來可能也不會有。」這說明瞭軟體開發是一個漸進的過程，需要不斷地迭代和改進。
許多經驗豐富的程式設計師都知道，寫出乾淨的程式碼需要先寫出「骯髒」的程式碼，然後再進行重構。Robert C. Martin 在《Clean Code》中指出，「大多數剛入行的程式設計師並不遵循這個建議，他們認為主要目標是讓程式執行起來，一旦它『能執行』了，他們就轉移到下一個任務。」這種做法實際上是一種專業上的自殺。
重構的實踐
在重構的過程中，我們需要不斷地測量和評估程式碼的可讀性和可維護性。Lord Kelvin 曾說，「當你能夠測量你所談論的東西並將其表示為數字時，你才真正瞭解它；但當你無法測量它，無法將其表示為數字時，你的知識是貧乏和不令人滿意的。」雖然我們無法直接測量可讀性，但我們可以透過評估別人理解程式碼所需時間來間接衡量它。
Kent Beck 在《Test-Driven Development》中提到，重構是一項艱苦的工作，有些程式非常難以編寫，以至於當它們終於執行時，我只想趕快完成它們，而不想重新設計它們。但當我第二年再回來看它們時，我很難理解自己的程式碼。
程式碼重構例項
考慮以下程式碼：
if x > 0:
if ch in {'A','B','C'}:
return True
else:
return False
else:
return False
內容解密：
這段程式碼檢查兩個條件：x 是否大於 0，以及 ch 是否在集合 {'A','B','C'} 中。如果兩個條件都滿足，則傳回 True，否則傳回 False。但是，這段程式碼存在多餘的條件判斷，可以簡化。
簡化後的程式碼如下：
return (x > 0) and (ch in {'A','B','C'})
內容解密：
簡化後的程式碼直接傳回兩個條件的邏輯與結果，避免了多餘的 if-else 結構，使程式碼更加簡潔和易讀。這種簡化不僅提高了程式碼的可讀性，也減少了出錯的可能性。
重構程式碼與邏輯最佳化
在軟體開發過程中，重構（Refactoring）是改善程式碼可讀性、可維護性和效能的重要步驟。本篇文章將探討如何透過重構來簡化複雜的條件陳述式、提升程式碼的可讀性，並避免常見的邏輯錯誤。
簡化使用者輸入處理
當需要使用者輸入特定選項時，可以採用簡單的輸入處理或更複雜但更穩健的方法。以下是一個簡單的範例：
def userChoice():
msg = ''
prompt = """
輸入 u 以執行 push 操作。
輸入 o 以執行 pop 操作。
輸入 v 以檢視內容。
輸入 q 或按下 Enter 鍵以離開。
請輸入您的選擇："""
while True:
try:
choice = input(msg + prompt).strip()[0].lower()
except:
return 'q'
if choice not in 'uovq':
msg = '錯誤："' + choice + '" 是無效的選擇。請再試一次。\n'
else:
return choice
內容解密：
while True迴圈：持續要求使用者輸入，直到獲得有效的選擇。try-except區塊：捕捉可能的輸入錯誤，例如空輸入。input(msg + prompt)：結合錯誤訊息（如果有的話）與提示訊息，要求使用者輸入。strip()[0].lower()：清理輸入，取得第一個字元並轉換為小寫，以進行後續的驗證。if choice not in 'uovq'：檢查輸入是否為有效的選項。
應用 DeMorgan 定律簡化條件判斷
DeMorgan 定律可以幫助簡化複雜的條件判斷，使程式碼更易讀。
原始程式碼：
for n in range(5):
if not A or x >= 10:
doSomething
簡化後：
for n in range(5):
if A and (x < 10):
continue
doSomething
內容解密：
not A or x >= 10：根據 DeMorgan 定律，等同於not (A and x < 10)。- 簡化邏輯：透過反轉條件並使用
continue，減少了巢狀結構，使程式碼更簡潔。
避免多重 if 陳述式
多重 if 陳述式可能導致邏輯錯誤，並使程式碼難以維護。以下是一個常見的錯誤範例：
x = 1
if x == 1: x = 2
if x == 2: x = 3
if x == 3: x = 4
print(x) # 輸出：4
更好的寫法是使用 elif 或 return/break/continue 陳述式來避免不必要的執行：
def doIt(x):
if x == 1:
return 2
elif x == 2:
return 3
elif x == 3:
return 4
內容解密：
elif使用：確保只有第一個符合條件的區塊被執行，避免後續條件幹擾。return陳述式：立即傳回結果，停止函式的進一步執行。
重構複雜條件陳述式
對於複雜的條件陳述式，可以透過垂直對齊 and 運算元或使用 Tuple 比較來提高可讀性。
原始程式碼：
if a == 1:
if b == 1:
if c == 1:
print('abc')
else:
print('ab-')
else:
if c == 1:
print('a-c')
else:
print('a--')
else:
if b == 1:
if c == 1:
print('-bc')
else:
print('-b-')
else:
if c == 1:
print('--c')
else:
print('
---
')
重構後：
if (a, b, c) == (1, 1, 1): print('abc')
if (a, b, c) == (1, 1, 0): print('ab-')
if (a, b, c) == (1, 0, 1): print('a-c')
if (a, b, c) == (1, 0, 0): print('a--')
if (a, b, c) == (0, 1, 1): print('-bc')
if (a, b, c) == (0, 1, 0): print('-b-')
if (a, b, c) == (0, 0, 1): print('--c')
if (a, b, c) == (0, 0, 0): print('
---
')
內容解密：
- Tuple 比較：將多個變數的比較簡化為一次 Tuple 比較，使條件判斷更直觀。
- 垂直對齊：透過對齊
if陳述式和條件，使程式碼結構更清晰。
二元搜尋演算法的測試與實作
二元搜尋是一種在已排序的列表中搜尋特定目標值的演算法。如果目標值存在於列表中，則傳回其索引；否則，傳回 -1。該演算法的時間複雜度為 O(log n)，使其在處理大規模資料時非常高效。
初始測試函式的設計
在實作二元搜尋演算法之前，設計一個簡單的測試函式（煙霧測試）至關重要。煙霧測試的主要目的是捕捉明顯的錯誤。
def binarySearchTest():
array = [0, 1, 2, 3, 4, 6, 7, 8, 9] # 注意：5 故意缺失
print('array =', array)
print('Test -9 =', binarySearch(array, -9) == -1)
print('Test 0 =', binarySearch(array, 0) == 0)
print('Test 4 =', binarySearch(array, 4) == 4)
print('Test 5 =', binarySearch(array, 5) == -1)
print('Test 9 =', binarySearch(array, 9) == 9)
print('Test 10 =', binarySearch(array, 10) == -1)
程式碼解析：
- 測試資料準備：建立一個已排序的列表
array，並故意缺失數字 5 以測試邊界條件。 - 多重測試案例：透過不同的測試案例驗證
binarySearch函式的正確性，包括查詢小於最小值、大於最大值、存在於列表中以及不存在於列表中的目標值。 - 輸出結果驗證：透過比較預期結果與實際結果來判斷
binarySearch函式是否正確。
二元搜尋演算法的實作
在透過初始測試後，我們可以開始實作二元搜尋演算法。
def binarySearch(array, target):
# 未檢查的前提條件：array 是已排序的整數列表
left = 0
right = len(array) - 1
while left < right:
mid = (left + right) // 2 # 向下取整
if array[mid] == target:
return mid
if array[mid] < target:
if left == mid:
left = left + 1
else:
left = mid
else:
right = mid
# 檢查空陣列或可能的解 left = right
if (array != []) and (array[left] == target):
return left # left = right = target 的索引
return -1 # 要麼 array = []，要麼 target 不在 array 中
程式碼解析：
- 初始化邊界：設定
left和right分別為列表的首尾索引。 - 二分查詢：透過不斷調整
left和right的值來縮小搜尋範圍，直到找到目標值或確定目標值不存在。 - 邊界條件處理：特別處理空列表以及
left和right相等的情況。
詳細測試與改進
為了進一步驗證二元搜尋演算法的正確性，我們可以進行更全面的測試。
def binarySearchTest():
runs = 1000 # 要測試的隨機陣列數量
# 用於驗證單個元素的 binarySearch 的函式
def check(array, value):
valueIndex = binarySearch(array, value)
if ((valueIndex == -1) and (value in array)) or \
((valueIndex != -1) and (array[valueIndex] != value)):
print('\n錯誤：array =', array)
print('值', value, '的傳回索引為', valueIndex)
exit()
# 檢查下面建立的所有隨機陣列中的所有數字
for i in range(runs):
# 建立不同大小和值的隨機陣列
arrayLength = randint(0, 30)
sm = randint(-5, 20) # sm = 陣列中可能的最小值
lg = randint(20, 40) # lg = 陣列中可能的最大值
array = sorted([randint(sm, lg) for j in range(0, arrayLength)])
# 測試陣列中的每個可能值以及一些不在陣列中的值
for value in range(sm-2, lg+2):
check(array, value)
print('正確：binarySearch 函式透過了', runs, '次測試。')
程式碼解析：
- 隨機測試資料生成：生成多個不同大小和值的隨機陣列，以全面測試
binarySearch函式。 - 詳細驗證邏輯：檢查每個目標值在陣列中的搜尋結果是否正確，確保函式的準確性。
