查找是比较常见的工作，今天我通过对比几种在数组中查找一个确定的值的例子来向大家展示二分查找的魅力。
数组查找元素的几种方法
使用List
1
2
3
|
public static boolean useList(String[] arr, String targetValue) {
return Arrays.asList(arr).contains(targetValue);
}
|
使用Set
1
2
3
4
|
public static boolean useSet(String[] arr, String targetValue) {
Set<String> set = new HashSet<String>(Arrays.asList(arr));
return set.contains(targetValue);
}
|
使用for-loop
1
2
3
4
5
6
7
|
public static boolean useLoop(String[] arr, String targetValue) {
for(String s: arr){
if(s.equals(targetValue))
return true;
}
return false;
}
|
使用二分
1
2
3
4
5
6
7
|
public static boolean useArraysBinarySearch(String[] arr, String targetValue) {
int a = Arrays.binarySearch(arr, targetValue);
if(a > 0)
return true;
else
return false;
}
|
时间复杂性
代码
使用如下代码来验证不同数据规模（5，1k，10k）的查找任务下四种方法的时间复杂性。（二分查找需要对数据排序，排序时间未计算在内。）
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
|
public static void main(String[] args) {
String[] arr = new String[] { "CD", "BC", "EF", "DE", "AB"};
long startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
useList(arr, "A");
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println("useList: " + duration / 1000000);
startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
useSet(arr, "A");
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("useSet: " + duration / 1000000);
startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
useLoop(arr, "A");
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("useLoop: " + duration / 1000000);
}
|
"5"结果
1
2
3
|
useList: 13
useSet: 72
useLoop: 5
|
"1k"结果
随机生成数据
1
2
3
4
5
6
|
String[] arr = new String[1000];
Random s = new Random();
for(int i=0; i< 1000; i++){
arr[i] = String.valueOf(s.nextInt());
}
|
结果
1
2
3
4
|
useList: 112
useSet: 2055
useLoop: 99
useArrayBinary: 12
|
"10k"结果
1
2
3
4
|
useList: 1590
useSet: 23819
useLoop: 1526
useArrayBinary: 12
|
结论
通过以上结果，我们可以发现二分搜索确实很高效，而且当数据量变大时，其时间增长幅度还比较小。
以后，我们就可以使用Arrays.binarySearch()来高效查找某元素了。
The link of this page is https://blog.nooa.tech/articles/fff444e8/ . Welcome to reproduce it!
