前置條件
- 陣列已排序（升序）。
- 若有重複元素，回傳任一匹配位置。
完整程式碼
#include
int zheban(int x, int arr[], int left, int right) {
while (left <= right) {
int mid = left + (right - left) / 2; // 避免溢位
if (x < arr[mid]) {
right = mid - 1;
} else if (x > arr[mid]) {
left = mid + 1;
} else {
return arr[mid]; // 找到，回傳值（亦可回傳索引 mid）
}
}
return -1; // 未找到
}
int main() {
int arr[8] = {1,2,3,4,5,6,7,8};
int size = sizeof(arr) / sizeof(arr[0]) - 1; // 最後索引 = 7
int ret = zheban(8, arr, 0, size);
if (ret == -1) {
printf("not exist!\n");
} else {
printf("%d\n", ret);
}
return 0;
}
關鍵點
mid = left + (right-left)/2：防止 left+right 整數溢位。- 迴圈條件
left <= right：確保單元素區間仍被檢查。
- 區間縮減：
right = mid-1 / left = mid+1 排除已檢查的 mid。
- 回傳值：示範回傳元素值，實務常回傳索引
mid 或布林值。
複雜度
