写出二分查找的递归算法

二分查找的递归算法如下：

1. 定义一个函数，传入一个有序数组、查找的元素、数组的起始位置和结束位置。

2. 计算数组的中间位置 mid，如果 mid 对应的元素等于查找的元素，则返回 mid。

3. 如果 mid 对应的元素大于查找的元素，则在数组的左半部分继续查找，即递归调用函数，传入数组、查找的元素、起始位置和 mid-1。

4. 如果 mid 对应的元素小于查找的元素，则在数组的右半部分继续查找，即递归调用函数，传入数组、查找的元素、mid+1 和结束位置。

5. 如果起始位置大于结束位置，则说明数组中不存在查找的元素，返回 -1。

6. 完成递归查找后，返回查找到的元素的下标。

代码实现如下：

int binarySearch(int arr[], int x, int low, int high) {
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
if (arr[mid] == x) {
return mid;
} else if (arr[mid] > x) {
return binarySearch(arr, x, low, mid - 1);
} else {
return binarySearch(arr, x, mid + 1, high);
}
}

相关问题

试写出折半查找的递归算法。

折半查找（二分查找）是一种非常高效的查找算法，但是它的递归实现相对来说比较复杂。以下是折半查找的递归算法：

def binary_search(arr, left, right, target):
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, mid + 1, right, target)
    else:
        return binary_search(arr, left, mid - 1, target)

以上代码中，`arr`是一个有序数组，`left`和`right`分别是数组的左右边界，`target`是要查找的目标元素。首先判断左右边界是否交叉，如果是则说明没有找到目标元素，返回-1。否则计算中间位置`mid`，如果中间位置的元素等于目标元素，则返回中间位置。如果中间位置的元素小于目标元素，则在右半部分继续查找。如果中间位置的元素大于目标元素，则在左半部分继续查找。这样就可以递归查找目标元素，直到找到为止。

使用Java语言用递归写一个二分查找算法

好的，那么你可以这样写:

public class BinarySearch {
  public static int binarySearch(int[] array, int target, int start, int end) {
    if (start > end) {
      return -1;
    }
    int mid = start + (end - start) / 2;
    if (array[mid] == target) {
      return mid;
    } else if (array[mid] < target) {
      return binarySearch(array, target, mid + 1, end);
    } else {
      return binarySearch(array, target, start, mid - 1);
    }
  }

  public static void main(String[] args) {
    int[] array = {1, 2, 3, 4, 5};
    int target = 4;
    int index = binarySearch(array, target, 0, array.length - 1);
    System.out.println("The target is at index: " + index);
  }
}

在这段代码中，我们使用了递归的方式来实现二分查找算法。在每一次递归中，我们都计算出数组的中间位置，然后根据目标值与中间位置的值的大小关系来决定将查找范围缩小到数组的前半部分还是后半部分。如果找到了目标值，则返回目标值的下标；如果查找范围已经缩小到了0，则表明目标值不存在，返回-1。