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

二分查找是一种高效的查找算法，也称作折半查找，属于有序查找算法。二分查找的原理是将有序数组分成两部分，每次查找可以减少一半的数据量，因此时间复杂度为O(log2n)。它是一种递归算法，本文将以Java语言实现二分查找的递归算法。

一、代码实现

二分查找的实现分为递归方式和非递归方式，本文将实现递归方式。代码实现如下：

```java

public class BinarySearch {

public static int binarySearch(int[] arr, int low, int high, int key) {

if (low <= high) {

int mid = (low + high) / 2;

if (arr[mid] == key) {

return mid;

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

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

} else {

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

}

}

return -1;

}

public static void main(String[] args) {

int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

int key = 8;

int result = binarySearch(arr, 0, arr.length - 1, key);

if (result != -1) {

System.out.println("查找结果为：" + result);

} else {

System.out.println("没有找到该元素");

}

}

}

```

二、代码解析

1. 二分查找函数

```java

public static int binarySearch(int[] arr, int low, int high, int key)

```

上述代码中binarySearch函数有四个参数，它们的含义分别为：

- arr：需要查找的数组；

- low：数组起始位置；

- high：数组结束位置；

- key：需要查找的元素。

2. 递归结束条件

```java

if (low <= high) {

// ...

}

```

当low大于high时，表示查找结束，返回-1。

3. 计算数组中间位置

```java

int mid = (low + high) / 2;

```

让low和high相加除以二，即可得到数组的中间位置mid。

4. 查找成功的情况

```java

if (arr[mid] == key) {

return mid;

}

```

如果查找的元素正好就是数组的中间位置上的元素，那么就直接返回mid。

5. 查找失败的情况

```java

else if (arr[mid] > key) {

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

} else {

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

}

```

如果查找的元素小于数组的中间位置上的元素，则在数组左半部分继续查找；如果查找的元素大于数组的中间位置上的元素，则在数组右半部分继续查找。

三、测试结果

上述代码通过传入数组arr和需要查找的元素key，返回查找结果的下标。测试结果如下：

1. 查找成功

假设需要查找的元素为8，程序输出结果为：

```

查找结果为：7

```

说明数组中第8个元素的下标为7，符合预期。

2. 查找失败

假设需要查找的元素为12，程序输出结果为：

```

没有找到该元素

```

说明数组中并没有该元素，符合预期。

四、总结

本文分析了如何使用Java实现二分查找的递归算法。由于二分查找是一种高效的查找算法，具有时间复杂度低的特点，因此在开发过程中经常用到。在实现二分查找时，需要注意递归结束条件的判断、计算数组中间位置的方法、查找成功和失败的情况处理。掌握了这些要点，就能够轻松地实现二分查找算法。