java二分查找算法
时间: 2024-06-12 18:02:31 浏览: 14
Java中的二分查找算法,也称为折半查找,是一种在有序数组中快速查找特定元素的搜索算法。它的基本思想是将数组分成两部分,每次都从中间元素开始比较,如果中间元素正好是要查找的目标值,则搜索结束;如果目标值小于中间元素,则在左半部分继续查找;如果目标值大于中间元素,则在右半部分查找。这个过程会一直持续到找到目标值或者数组被分成的子集为空。
以下是二分查找算法的基本步骤:
1. 初始化两个指针,`low`(代表左边界)和`high`(代表右边界),初始时`low`为0,`high`为数组长度减1。
2. 计算中间索引`mid`,通常是 `low + (high - low) / 2`。
3. 检查中间元素`arr[mid]`是否等于目标值`target`。
a. 如果相等,返回`mid`作为结果。
b. 如果`target`小于`arr[mid]`,说明目标在左半部分,更新`high`为`mid - 1`。
c. 如果`target`大于`arr[mid]`,说明目标在右半部分,更新`low`为`mid + 1`。
4. 重复步骤2和3,直到`low`大于`high`,说明目标不存在于数组中,返回-1表示未找到。
相关问题
java二分查找算法代码
以下是Java中的二分查找算法代码示例:
```java
public static int binarySearch(int[] arr, int target) {
int start =0;
int end = arr.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return -1; // target不在数组中
}
```
此代码接收一个有序整数数组和一个目标整数,返回目标整数在数组中的索引,如果目标整数不在数组中,则返回-1。该算法采用迭代的方式实现。
Java 实现二分查找算法
二分查找算法,也叫折半查找算法,是一种效率较高的查找算法。它需要在已排好序的数组中查找一个特定元素,时间复杂度为 O(log n)。
以下是 Java 实现二分查找算法的示例代码:
```java
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}
```
其中,`arr` 为已排好序的数组,`target` 为要查找的特定元素。`left` 和 `right` 分别表示查找区间的左右边界,初始时 `left` 为 0,`right` 为数组的最后一个元素的下标。在循环中,每次找到中间的元素 `mid`,然后与目标元素 `target` 进行比较,如果相等则返回 `mid`,如果 `arr[mid] < target`,则说明目标元素在 `mid` 的右侧,修改 `left` 的值为 `mid + 1`,否则说明目标元素在 `mid` 的左侧,修改 `right` 的值为 `mid - 1`。最后,若没有找到目标元素,则返回 -1。
示例调用代码:
```java
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9};
int target = 5;
int index = BinarySearch.binarySearch(arr, target);
if (index == -1) {
System.out.println("查找失败!");
} else {
System.out.println("目标元素在数组中的下标为:" + index);
}
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![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)