递归实现二分查找算法
时间: 2024-06-13 12:04:27 浏览: 12
递归实现二分查找算法是一种高效的搜索算法,适用于已排序的数组。该算法通过递归的方式将数组不断二分,直到找到目标元素或者确定目标元素不存在为止。具体实现可以参考以下示例代码:
int binarySearch(int arr[], int low, int high, int target) {
if (low > high) {
return -1; // 查找失败,返回-1
}
int mid = low + (high - low) / 2; // 计算中间元素的下标
if (arr[mid] == target) {
return mid; // 找到目标元素,返回下标
} else if (arr[mid] > target) {
return binarySearch(arr, low, mid - 1, target); // 目标元素在左半部分,继续递归查找
} else {
return binarySearch(arr, mid + 1, high, target); // 目标元素在右半部分,继续递归查找
}
}
在该示例代码中,函数binarySearch接收四个参数:数组arr、数组的起始下标low、数组的结束下标high和目标元素target。函数首先判断low是否大于high,如果是则返回-1表示查找失败;否则计算中间元素的下标mid,如果中间元素等于目标元素,则返回mid表示查找成功;如果中间元素大于目标元素,则在左半部分继续递归查找;如果中间元素小于目标元素,则在右半部分继续递归查找。