如何用java实现二分算法
时间: 2023-03-15 21:38:44 浏览: 53
Java中可以使用递归或迭代的方法实现二分算法。递归的实现方式是根据数组的中间元素的值与要查找的值进行比较,如果相等,则查找成功;如果要查找的值比中间元素的值小,则在数组的左半部分查找;如果要查找的值比中间元素的值大,则在数组的右半部分查找。迭代的实现方式是使用两个指针,一个指向数组的起始位置,另一个指向数组的末尾位置,比较这两个指针指向的元素的值与要查找的值,如果相等,则查找成功;如果要查找的值比这两个指针指向的元素的值都小,则移动左指针;如果要查找的值比这两个指针指向的元素的值都大,则移动右指针。
相关问题
用java实现二分算法
可以使用以下代码实现二分算法:
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
java实现二分查找算法
以下是 Java 实现的二分查找算法:
```java
public static int binarySearch(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
```
其中,`arr` 是已排序的数组,`target` 是要查找的目标值。算法使用两个指针 `low` 和 `high` 来定义当前的搜索范围,初始时指向数组的第一个和最后一个元素。在每一轮迭代中,算法计算当前搜索范围的中间位置 `mid`,并根据 `arr[mid]` 与 `target` 的大小关系来更新指针 `low` 和 `high`。如果找到了目标值,算法返回其索引;否则,如果搜索范围已经缩小到只有一个元素,仍然没有找到目标值,则算法返回 -1 表示搜索失败。