SearchTest.java
2.11 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
77
78
79
80
81
82
83
84
package com.bootdo.common.utils.search;
import java.util.Date;
public class SearchTest {
public static void main(String[] args) {
int [] a = randomCommon(1,10000,8000);
int b = 4889;
Date d1 = new Date();
System.out.println("普通查找，结果为："+sequentialSearch(a,b));
Date d2 = new Date();
System.out.println("普通查找，耗时："+(d2.getTime()-d1.getTime()));
Date d3 = new Date();
System.out.println("哨兵查找，结果为："+sequentialSearchSentry(a,b));
Date d4 = new Date();
System.out.println("哨兵查找，耗时："+(d4.getTime()-d3.getTime()));
// int k=0;
// for(int i=0;i<10;i++) {
// System.out.println("外循环.."+i);
// for(int j=i;j<10;j++) {
// System.out.println((k++)+"..."+j);
// }
// }
}
//顺序查找---普通，找到了返回数组中的下标，没找到返回-1
private static int sequentialSearch(int [] a, int key) {
for(int i=0;i<a.length;i++) {
if(a[i]==key) {
return i;
}
}
return -1;
}
//顺序查找---哨兵，找到了返回数组中的下标，没找到返回-1
private static int sequentialSearchSentry(int [] a, int key) {
a[0]=key;
int i= a.length-1;
while(a[i]!=key) {
i--;
}
return i==0?i-1:i;
}
/**
* 随机指定范围内N个不重复的数
* 最简单最基本的方法
* @param min 指定范围最小值
* @param max 指定范围最大值
* @param n 随机数个数
*/
public static int[] randomCommon(int min, int max, int n){
if (n > (max - min + 1) || max < min) {
return null;
}
int[] result = new int[n];
int count = 0;
while(count < n) {
int num = (int) (Math.random() * (max - min)) + min;
boolean flag = true;
for (int j = 0; j < n; j++) {
if(num == result[j]){
flag = false;
break;
}
}
if(flag){
result[count] = num;
count++;
}
}
return result;
}
}