java二分查找递归算法
时间: 2023-05-11 09:05:11 浏览: 94
二分查找是一种常见的查找算法,它可以在有序数组中快速查找指定元素。递归算法是一种常见的实现方式,其基本思路是将数组分成两部分,如果中间元素等于目标元素,则返回中间元素的下标;如果中间元素大于目标元素,则在左半部分继续查找;如果中间元素小于目标元素,则在右半部分继续查找。以下是 Java 语言实现的二分查找递归算法:
```
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);
}
}
```
其中,arr 表示有序数组,target 表示目标元素,left 表示左边界,right 表示右边界。初始时,left 为 0,right 为数组长度减一。如果查找成功,则返回目标元素的下标;否则返回 -1。
相关问题
java二分查找递归
Java中的二分查找算法可以使用递归来实现。二分查找是一种高效的查找算法,适用于有序数组。
以下是Java中使用递归实现二分查找的代码示例:
```java
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
return binarySearch(arr, target, 0, arr.length - 1);
}
private 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, 2, 3, 4, 5, 6, 7, 8, 9};
int target = 6;
int result = binarySearch(arr, target);
if (result == -1) {
System.out.println("目标元素不存在");
} else {
System.out.println("目标元素的索引为:" + result);
}
}
}
```
上述代码中,`binarySearch`方法是对外暴露的接口,它调用了私有的`binarySearch`方法来实现递归查找。在每一次递归调用中,通过计算中间元素的索引,将查找范围缩小一半,直到找到目标元素或者查找范围为空。
java递归算法实现二分查找
递归算法实现二分查找的Java代码可以参考以下示例:
```java
public class BinarySearch {
public static void main(String[] args) {
int[] nums = {1, 2, 6, 15, 18, 20, 25, 27, 35, 40, 45, 56, 62, 78, 88};
int findValue = 35;
int binaryResult = binarySearch(nums, 0, nums.length - 1, findValue);
System.out.println("元素第一次出现的位置(从0开始):" + binaryResult);
}
private static int binarySearch(int[] nums, int start, int end, int findValue) {
if (start <= end) {
int middle = (start + end) / 2;
if (findValue == nums[middle]) {
return middle; // 查找值等于中间值直接返回
} else if (findValue < nums[middle]) {
return binarySearch(nums, start, middle - 1, findValue); // 小于中间值,在中间值之前的数据中查找
} else {
return binarySearch(nums, middle + 1, end, findValue); // 大于中间值,在中间值之后的数据中查找
}
}
return -1;
}
}
```
这个递归实现的二分查找算法首先检查开始下标`start`是否小于等于结束下标`end`,如果是,则计算中间下标`middle`。然后通过比较查找值`findValue`与中间值`nums[middle]`的大小,决定是在中间值之前的数据中查找还是在中间值之后的数据中查找,递归调用`binarySearch`方法。如果查找值等于中间值,则直接返回中间下标;如果查找值小于中间值,则在中间值之前的数据中查找,更新结束下标`end`为`middle - 1`;如果查找值大于中间值,则在中间值之后的数据中查找,更新开始下标`start`为`middle + 1`。如果开始下标大于结束下标,表示未找到查找值,返回-1。
这样的递归实现方式能够不断缩小查找范围,提高查找效率。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* [二分查找递归解法(java)](https://blog.csdn.net/weixin_51577444/article/details/123763009)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
- *2* *3* [Java常用算法-二分查找算法(两种方法实现)](https://blog.csdn.net/zengqing2010/article/details/120680127)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)