用JAVA语言写一段代码,通过递归算法实现折半查找问题
时间: 2023-05-11 08:04:35 浏览: 69
当然可以,以下是Java语言实现折半查找的递归算法代码:
public static int binarySearch(int[] arr, int target, int left, int right) {
if (left > right) {
return -1;
}
int mid = (left + right) / 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为数组右边界。如果找到了目标值,则返回其下标,否则返回-1。
相关问题
数据结构的折半查找算法:分别使用递归和非递归算法实现查找
好的,我会为您解答。首先,折半查找算法也被称为二分查找算法,是一种高效的查找算法,适用于已排序的数据集合。以下是使用递归和非递归算法实现折半查找的代码示例。
1. 递归算法实现:
```python
def binary_search_recursive(arr, low, high, x):
if high >= low:
mid = (high + low) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search_recursive(arr, low, mid - 1, x)
else:
return binary_search_recursive(arr, mid + 1, high, x)
else:
return -1
```
2. 非递归算法实现:
```python
def binary_search_iterative(arr, x):
low = 0
high = len(arr) - 1
while low <= high:
mid = (high + low) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
high = mid - 1
else:
low = mid + 1
return -1
```
在这两种实现中,我们都使用了一个辅助函数来计算中间元素的索引。在递归算法中,我们首先比较中间元素与要查找的元素,如果相等则返回中间元素的索引,否则我们根据中间元素的值来选择左半部分或右半部分进行递归查找。在非递归算法中,我们使用while循环来迭代查找,直到找到要查找的元素或搜索空间缩小为空。
希望这个解答对您有所帮助!
使用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。