2.编写 Java程序, 设计MyArray2类来实现以下要求: 使用二分法查询数组中的元素是否存在。数组元素个数可以由用户确定, 数组元素值也可由用户输入; 注意: 采用二分法对数组查询的前提条件是要求数组有序;
时间: 2024-11-09 07:21:29 浏览: 26
为了实现MyArray2类,我们需要确保它是一个动态数组并且能够维护有序性,以便应用二分查找算法。下面是一个简单的示例,说明如何设计这样的类:
```java
import java.util.ArrayList;
import java.util.Arrays;
public class MyArray2<T extends Comparable<T>> {
private ArrayList<T> array; // 使用ArrayList以支持动态添加元素
public MyArray2(int size) {
array = new ArrayList<>(size); // 创建初始有序列表
}
// 添加元素并保持有序
public boolean add(T element) {
if (array.isEmpty()) {
array.add(element);
return true;
} else {
int index = binarySearch(array, element);
if (index == -1) {
array.add(index, element);
return true;
} else {
return false; // 元素已存在,无需添加
}
}
}
// 二分查找
private int binarySearch(ArrayList<T> sortedList, T target) {
int left = 0;
int right = sortedList.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int comparison = sortedList.get(mid).compareTo(target);
if (comparison == 0) {
return mid;
} else if (comparison < 0) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 目标元素不存在于数组中
}
// 检查元素是否存在于数组中
public boolean contains(T target) {
return binarySearch(array, target) != -1;
}
// 其他相关方法,如显示数组等
public static void main(String[] args) {
MyArray2<Integer> integerArray = new MyArray2<>(5);
// 输入元素并添加到数组
for (int i = 0; i < 5; i++) {
int input = getUserInput();
integerArray.add(input);
}
// 查找元素是否存在
int searchElement = getUserInput();
System.out.println("元素 " + searchElement + " 是否在数组中?" + (integerArray.contains(searchElement) ? "是" : "否"));
}
private static int getUserInput() {
Scanner scanner = new Scanner(System.in);
System.out.print("请输入一个整数值:");
return scanner.nextInt();
}
}
```
在这个`MyArray2`类中,我们使用`ArrayList`作为内部数据结构,因为其允许动态添加元素。`add`方法负责插入新元素并保持数组有序,`binarySearch`方法实现了二分查找。`contains`方法则是基于二分查找来检查目标元素是否存在。
阅读全文