递归int binarysearch(int a[],int first,int last,int target)查找给定的数值target是否在数组a中JAVA
时间: 2024-09-25 13:16:20 浏览: 61
递归二分搜索(binary search)是一种在排序数组`a`中查找目标值`target`的算法,它通过不断将数组分成两半来缩小搜索范围。在Java中,递归的二分搜索函数可以这样定义:
```java
public int binarySearch(int[] a, int first, int last, int target) {
// 如果first大于last,说明没有找到目标,返回-1
if (first > last) {
return -1;
}
// 计算中间索引
int mid = first + (last - first) / 2;
// 检查中间元素是否等于目标,如果相等则返回索引
if (a[mid] == target) {
return mid;
}
// 否则,如果目标小于中间元素,对左半部分继续搜索
else if (a[mid] > target) {
return binarySearch(a, first, mid - 1, target);
}
// 否则,如果目标大于中间元素,对右半部分继续搜索
else {
return binarySearch(a, mid + 1, last, target);
}
}
```
这个函数接受四个参数:
1. `a`: 排序后的整数数组
2. `first`: 数组的第一个搜索位置
3. `last`: 数组的最后一个搜索位置(不包括)
4. `target`: 需要查找的目标值
递归结束条件是`first`大于`last`,这意味着没有找到目标,函数返回-1。
阅读全文