1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
| /**
* 二分查找算法综合测试
*/
public class BinarySearchTest {
public static void main(String[] args) {
System.out.println("=== 二分查找算法综合测试 ===");
testBasicBinarySearch();
testBinarySearchVariants();
testBinaryAnswer();
testBinarySearchTree();
testOrderedSet();
testOptimizations();
}
private static void testBasicBinarySearch() {
System.out.println("\n1. 基础二分查找测试:");
int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int target = 7;
System.out.println("迭代版本:");
int result1 = BinarySearch.binarySearchIterative(arr, target);
System.out.println("\n递归版本:");
int result2 = BinarySearch.binarySearchRecursive(arr, target, 0, arr.length - 1);
System.out.println("结果: " + result1 + ", " + result2);
}
private static void testBinarySearchVariants() {
System.out.println("\n2. 二分查找变种测试:");
int[] arr = {1, 2, 2, 2, 3, 4, 4, 5, 5, 5, 6};
int target = 2;
System.out.println("数组: " + Arrays.toString(arr));
System.out.println("目标: " + target);
int first = BinarySearchVariants.findFirst(arr, target);
int last = BinarySearchVariants.findLast(arr, target);
int lower = BinarySearchVariants.lowerBound(arr, target);
int upper = BinarySearchVariants.upperBound(arr, target);
System.out.println("第一个位置: " + first);
System.out.println("最后位置: " + last);
System.out.println("下界: " + lower);
System.out.println("上界: " + upper);
// 测试旋转数组
int[] rotated = {4, 5, 6, 7, 0, 1, 2};
int rotatedResult = BinarySearchVariants.searchInRotatedArray(rotated, 0);
System.out.println("旋转数组中查找0: " + rotatedResult);
}
private static void testBinaryAnswer() {
System.out.println("\n3. 二分答案测试:");
// 分割数组测试
int[] nums = {7, 2, 5, 10, 8};
int m = 2;
int result = BinaryAnswer.splitArray(nums, m);
// 香蕉问题测试
int[] piles = {3, 6, 7, 11};
int h = 8;
int speed = BinaryAnswer.minEatingSpeed(piles, h);
}
private static void testBinarySearchTree() {
System.out.println("\n4. 二分查找树测试:");
BinarySearchTree bst = new BinarySearchTree();
int[] values = {5, 3, 7, 2, 4, 6, 8};
for (int val : values) {
bst.insert(val);
}
System.out.println("查找5: " + bst.search(5));
System.out.println("查找10: " + bst.search(10));
System.out.println("第3小元素: " + bst.kthSmallest(3));
System.out.println("是否为有效BST: " + bst.isValidBST());
}
private static void testOrderedSet() {
System.out.println("\n5. 有序集合测试:");
OrderedSet set = new OrderedSet();
int[] values = {5, 2, 8, 1, 9, 3};
for (int val : values) {
set.add(val);
}
set.display();
System.out.println("包含5: " + set.contains(5));
System.out.println("小于5的最大元素: " + set.lower(5));
System.out.println("大于5的最小元素: " + set.higher(5));
System.out.println("范围[3,7]: " + set.range(3, 7));
}
private static void testOptimizations() {
System.out.println("\n6. 优化技术测试:");
int[] largeArr = new int[1000000];
for (int i = 0; i < largeArr.length; i++) {
largeArr[i] = i * 2;
}
int target = 999998;
// 比较不同搜索算法的性能
long start = System.nanoTime();
int result1 = BinarySearch.binarySearchIterative(largeArr, target);
long time1 = System.nanoTime() - start;
start = System.nanoTime();
int result2 = CacheFriendlyBinarySearch.blockBinarySearch(largeArr, target);
long time2 = System.nanoTime() - start;
start = System.nanoTime();
int result3 = CacheFriendlyBinarySearch.interpolationSearch(largeArr, target);
long time3 = System.nanoTime() - start;
System.out.println("普通二分查找: " + time1 / 1000.0 + " μs, 结果: " + result1);
System.out.println("分块二分查找: " + time2 / 1000.0 + " μs, 结果: " + result2);
System.out.println("插值搜索: " + time3 / 1000.0 + " μs, 结果: " + result3);
}
}
|