二分查找(递归实现)
时间: 2024-01-11 08:21:32 浏览: 43
以下是二分查找的递归实现的代码示例:
```python
def binary_search(arr, left, right, key):
if left > right:
return -1
mid = (left + right) // 2
if key > arr[mid]:
return binary_search(arr, mid + 1, right, key)
elif key < arr[mid]:
return binary_search(arr, left, mid - 1, key)
else:
return mid
```
这段代码使用递归的方式实现了二分查找算法。它接受一个有序数组arr、左边界left、右边界right和要查找的关键字key作为参数。首先,它检查左边界是否大于右边界,如果是,则返回-1表示未找到。然后,它计算中间元素的索引mid,并将关键字与中间元素进行比较。如果关键字大于中间元素,则在右半部分继续递归查找;如果关键字小于中间元素,则在左半部分继续递归查找;如果关键字等于中间元素,则返回中间元素的索引。通过递归调用,直到找到关键字或确定未找到为止。
相关问题
线性结构 二分查找递归实现和排序 c语言代码
二分查找是一种高效的查找算法,其基本思想是在有序数组中查找某个元素时,每次取中间位置的值进行比较,如果该值大于目标元素,则在左半部分继续查找,否则在右半部分查找,直到查找到目标元素或者数组中不存在该元素为止。以下是二分查找的递归实现和排序的C语言代码示例:
```c
// 二分查找递归实现
int binarySearch(int arr[], int low, int high, int target) {
if (low > high) {
return -1;
}
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
return binarySearch(arr, mid+1, high, target);
} else {
return binarySearch(arr, low, mid-1, target);
}
}
// 快速排序
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot-1);
quickSort(arr, pivot+1, high);
}
}
// 快速排序辅助函数
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i+1], &arr[high]);
return i+1;
}
```
在上述代码中,我们首先定义了一个二分查找的递归实现函数 binarySearch(),其中 arr[] 表示有序数组,low 和 high 分别表示数组的起始和结束位置,target 表示要查找的目标元素。在函数中,我们先计算出数组的中间位置 mid,如果中间位置的值等于目标元素,则直接返回 mid,否则根据中间位置的值和目标元素的大小关系来决定在左半部分还是右半部分进行查找。如果数组中不存在目标元素,则返回 -1。
接下来,我们定义了一个快速排序的函数 quickSort(),其中 low 和 high 分别表示数组的起始和结束位置。在函数中,我们先通过 partition() 函数将数组分为两部分,然后对左半部分和右半部分分别进行递归排序。partition() 函数用于将数组分为两部分,其中 pivot 表示基准元素,i 表示分界点,j 表示当前遍历到的位置。在遍历过程中,如果当前位置的值小于基准元素,则将其移动到分界点的左边。最终,将基准元素移动到分界点,并返回分界点的位置。
二分查找Java 递归实现
以下是Java中递归实现二分查找的代码示例:
```java
public class BinarySearch {
public static int binarySearch(int[] arr, int target, int left, int right) {
if (left > right) {
return -1;
}
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] > target) {
return binarySearch(arr, target, left, mid - 1);
} else {
return binarySearch(arr, target, mid + 1, right);
}
}
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9};
int target = 3;
int result = binarySearch(arr, target, 0, arr.length - 1);
if (result == -1) {
System.out.println("Element not present");
} else {
System.out.println("Element found at index " + result);
}
}
}
```