二分查找
//递归法
int binary_search(const int arr[], int start, int end, int khey) {
if (start > end)
return -1;
int mid = start + (end - start) / 2;
if (arr[mid] > khey)
return binary_search(arr, start, mid - 1, khey);
else if (arr[mid] < khey)
return binary_search(arr, mid + 1, end, khey);
else
return mid;
}
//while 循环法
int binary_search(const int arr[], int start, int end, int key) {
int ret = -1;
int mid;
while (start <= end) {
mid = start + (end - start) / 2;
if (arr[mid] < key)
start = mid + 1;
else if (arr[mid] > key)
end = mid - 1;
else {
ret = mid;
break;
}
}
return ret;
}