前導
二分搜尋法（Binary Search）是一種 高效的搜尋演算法，適用於 已排序 的資料結構。 它的核心思想是 每次將搜尋範圍減半，直到找到目標值或範圍縮小到無法繼續搜尋。
演算法步驟
- 確認資料已排序（若未排序，需先排序）。
- 設定 左邊界 (low) 為
0，右邊界 (high) 為陣列長度 - 1。 - 計算中間索引 (mid)：
- 比較
arr[mid]與target：
- 若
arr[mid] == target，則返回索引mid（找到目標）。 - 若
arr[mid] > target，則high = mid - 1（縮小到左半區間）。 - 若
arr[mid] < target，則low = mid + 1（縮小到右半區間）。
- 若
- 重複第三步驟和第四步驟。
- 若
low>high，表示目標值 不存在，返回 -1。
程式碼
#include <stdio.h>
int binarySearch(int arr[], int size, int target) {
int low = 0, high = size - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
printf("low = %d, high = %d, mid = %d, arr[mid] = %d\n", low, high, mid, arr[mid]);
if (arr[mid] == target) {
return mid; // 找到目標，返回索引
}
if (arr[mid] < target) {
low = mid + 1; // 搜尋右半部
} else {
high = mid - 1; // 搜尋左半部
}
}
return -1; // 找不到
}
int main() {
int arr[] = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72}; // 已排序數列
int size = sizeof(arr) / sizeof(arr[0]);
int target = 23;
int result = binarySearch(arr, size, target);
if (result != -1) {
printf("找到 %d，索引位置為 %d\n", target, result);
} else {
printf("未找到 %d\n", target);
}
return 0;
}
- 與 循序搜尋法 相比，二分搜尋法的效率大幅提升。
