java实现二分查找的递归算法

二分查找算法（Binary Search）也叫折半查找算法，它是一种重要的查找算法，常用于搜索有序数组和列表中的元素。本文将重点介绍Java语言实现二分查找的递归算法。

1. 算法思想

二分查找的基本思想是将查找区间不断缩小一半，直到找到目标元素或查找范围为空。如果数组有序，那么可以采用二分查找算法，如下：

（1）首先，对数组进行排序；

（2）将数组中间位置的值与要查找的值进行比较；

（3）如果要查找的值小于中间值，则在数组左边继续查找；

（4）如果要查找的值等于中间值，则查找成功；

（5）如果要查找的值大于中间值，则在数组右边继续查找。

上述过程可以采用递归算法实现，在每次查找时将数组分为两半进行递归查找，直到查找到目标元素或查找区间为空。

2. 算法实现

（1）非递归实现

在Java实现非递归的二分查找算法时，需要定义三个变量：left、right、mid。left表示要查找的范围的左端点，right表示要查找的范围的右端点，mid为中间位置。

- 算法步骤如下：

（1）在要查找的范围内，获取中间位置 mid = (left + right) / 2；

（2）将中间位置的值与要查找的值进行比较，如果要查找的值等于中间位置的值，则返回查找的下标位置；

（3）如果要查找的值小于中间位置的值，则在左侧继续查找，令 right = mid - 1；

（4）如果要查找的值大于中间位置的值，则在右侧继续查找，令 left = mid + 1；

（5）如果查找的区间为空，则返回 -1；

（6）重复步骤1~5，直到查找到目标元素或查找范围为空。

（2）递归实现

在Java实现递归的二分查找算法时，需要定义三个参数：数组 arr、要查找的值 key、要查找范围的左端点和右端点 left、right。

- 算法步骤如下：

（1）在要查找的范围内，获取中间位置 mid = (left + right) / 2；

（2）将中间位置的值与要查找的值进行比较，如果要查找的值等于中间位置的值，则返回查找的下标位置；

（3）如果要查找的值小于中间位置的值，则在左侧继续查找，令 right = mid - 1，并对从 left ~ mid - 1 范围内的数组进行递归查找；

（4）如果要查找的值大于中间位置的值，则在右侧继续查找，令 left = mid + 1，并对从 mid + 1 ~ right 范围内的数组进行递归查找；

（5）如果查找的区间为空，则返回 -1；

（6）重复步骤1~5，直到查找到目标元素或查找范围为空。

下面是Java的递归实现代码：

```java

public static int binarySearch(int[] arr, int key, int left, int right) {

if (left > right) {

return -1;

}

int mid = (left + right) / 2;

if (arr[mid] == key) {

return mid;

} else if (arr[mid] > key) {

return binarySearch(arr, key, left, mid - 1);

} else {

return binarySearch(arr, key, mid + 1, right);

}

}

public static void main(String[] args) {

int[] arr = {1, 3, 5, 7, 9};

int index = binarySearch(arr, 7, 0, arr.length - 1);

System.out.println(index);

}

```

上述代码可以在有序数组中查找目标值，如果查找成功，则返回目标值在数组中的下标；如果查找失败，则返回 -1。

3. 算法优化

在实际应用中，如果数组元素较多，则递归过程会频繁地压栈和出栈，耗费大量的时间和内存。为了优化算法性能，可以采用非递归的实现方式。

另外需要注意的是，在使用二分查找算法时，必须要求数组是有序的，否则查找结果会出错。

4.