编写程序,实现对单调递增的整形序列中(如随机产生10个1~100之间的不重复整数序列),进行折半查找。用折半查找法找出一个数是数组中第几个元素,如果找到,则返回其下标,如果该数不在数组中,则返回-1
时间: 2024-09-13 09:07:13 浏览: 47
折半查找的基本思想-东南大学C++何洁月
折半查找,也称为二分查找,是一种在有序数组中查找特定元素的高效算法。其基本思想是将数组分成两半,首先与中间元素比较,如果相等则返回该元素的位置,如果要查找的元素小于中间元素,则在数组的左半部分继续查找,反之则在右半部分查找,递归或重复上述过程直到找到元素或者查找范围为空。
下面是使用Java编写的一个折半查找的示例代码:
```java
public class BinarySearchExample {
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; // 未找到目标值,返回-1
}
public static void main(String[] args) {
int[] arr = {5, 12, 19, 23, 30, 37, 45, 52, 61, 71}; // 示例数组
int target = 37; // 查找的目标值
int result = binarySearch(arr, target);
System.out.println("元素的位置: " + result);
}
}
```
在上述代码中,`binarySearch` 方法接受一个有序数组 `arr` 和一个目标值 `target`,通过不断将查找范围缩小一半的方式,最终找到目标值的位置或者返回 `-1` 表示未找到。
阅读全文