java实现数组二分查找
时间: 2024-08-13 19:01:04 浏览: 27
Java 实现数组二分查找是一种高效搜索算法,适用于已排序的数组。其基本思想是在每次迭代过程中都将数组分成两部分,然后根据中间元素与目标值的关系缩小搜索范围。以下是 Java 中实现二分查找的一种常见方法:
```java
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
if (arr == null || arr.length == 0) {
return -1; // 如果数组为空,则返回-1表示未找到
}
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 防止计算mid时溢出
if (arr[mid] == target) {
return mid; // 找到目标值,返回下标
} else if (arr[mid] < target) {
left = mid + 1; // 目标值在右半边
} else {
right = mid - 1; // 目标值在左半边
}
}
return -1; // 没有找到目标值
}
public static void main(String[] args) {
int[] sortedArray = {1, 3, 5, 7, 9};
int target = 5;
int result = binarySearch(sortedArray, target);
System.out.println("Target found at index: " + result);
target = 6;
result = binarySearch(sortedArray, target);
System.out.println("Target not found.");
}
}
```
上述代码中定义了一个名为 `binarySearch` 的函数,用于在已排序的整数数组 `arr` 中查找特定的目标值 `target`。如果找到目标值,则返回其索引;如果没有找到,则返回 `-1`。
此算法的时间复杂度为 O(log n),其中 n 是数组的长度。因为每次迭代都会将搜索区间减半,所以效率非常高,尤其是在处理大量数据时。
---
相关问题:
1. 为什么在查找有序数组时通常使用二分查找而非线性查找?
2. 如何优化数组二分查找性能?
3. 二分查找对输入数组有哪些限制条件?
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.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)
![](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)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)