forked from algorithmzuo/algorithmbasic2020
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCode06_BSAwesome.java
More file actions
76 lines (70 loc) · 1.79 KB
/
Code06_BSAwesome.java
File metadata and controls
76 lines (70 loc) · 1.79 KB
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
package class01;
public class Code06_BSAwesome {
// 课上的代码
public static int getLessIndex(int[] arr) {
if (arr == null || arr.length == 0) {
return -1;
}
if (arr.length == 1 || arr[0] < arr[1]) {
return 0;
}
if (arr[arr.length - 1] < arr[arr.length - 2]) {
return arr.length - 1;
}
int left = 1;
int right = arr.length - 2;
int mid = 0;
while (left < right) {
mid = (left + right) / 2;
if (arr[mid] > arr[mid - 1]) {
right = mid - 1;
} else if (arr[mid] > arr[mid + 1]) {
left = mid + 1;
} else {
return mid;
}
}
return left;
}
// 验证得到的结果，是不是局部最小
public static boolean isRight(int[] arr, int index) {
if (arr.length <= 1) {
return true;
}
if (index == 0) {
return arr[index] < arr[index + 1];
}
if (index == arr.length - 1) {
return arr[index] < arr[index - 1];
}
return arr[index] < arr[index - 1] && arr[index] < arr[index + 1];
}
// 为了测试
// 生成相邻不相等的数组
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) (Math.random() * maxSize) + 1];
arr[0] = (int) (Math.random() * maxValue) - (int) (Math.random() * maxValue);
for (int i = 1; i < arr.length; i++) {
do {
arr[i] = (int) (Math.random() * maxValue) - (int) (Math.random() * maxValue);
} while (arr[i] == arr[i - 1]);
}
return arr;
}
// 为了测试
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 30;
int maxValue = 100;
System.out.println("测试开始");
for (int i = 0; i < testTime; i++) {
int[] arr = generateRandomArray(maxSize, maxValue);
int ans = getLessIndex(arr);
if (!isRight(arr, ans)) {
System.out.println("出错了！");
break;
}
}
System.out.println("测试结束");
}
}