书山有路勤为径,学海无涯苦作舟。

0%

Java二分法查找

最近遇到一个问题:

须要在20万号段数据中查找对应的地市,并且这个过程是发生在遍历几百万数据中的。也就是说正常情况下须要执行20万*几百万次。

这个时间太久了,且因为号段是长数字,执行起来速度超慢。

后来突然想到可以用二分法。

二分法的原理就是:把有序的数据分为2段,通过比较得到数据在哪段,然后再把这段的数据分为2段,这样就省去了很多不必要的遍历,复杂度O(logn)。

下面两个例子就是二分法的示例,一个是递归,一个是循环。

java二分法循环示例

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
package cn.sunzn.dichotomy;

public class DichotomySearch {
public static void main(String[] args) {
int[] arr = new int[] { 12, 23, 34, 45, 56, 67, 77, 89, 90 };
System.out.println(search(arr, 12));
System.out.println(search(arr, 45));
System.out.println(search(arr, 67));
System.out.println(search(arr, 89));
System.out.println(search(arr, 99));
}

public static int search(int[] arr, int key) {
int start = 0;
int end = arr.length - 1;
while (start <= end) {
int middle = (start + end) / 2;
if (key < arr[middle]) {
end = middle - 1;
} else if (key > arr[middle]) {
start = middle + 1;
} else {
return middle;
}
}
return -1;
}
}

java二分法递归示例

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
/**
* 二分法查找,必须对已经排好序的序列进行查找,假设现在有一个递增序列,取中间位置的数及序号midIndex=(beginIndex+endIndex)/2,
* 然后将一个序列折成两半,beginIndex~midIndex,midIndex~endIndex,如果目标数T等于S[midIndex],找到,
* 否则,如果T<S[midIndex],则在beginIndex~midIndex中继续查找;如果T>S[midIndex],则在midIndex~endIndex
* 中继续查找,如此反复进行,直到找到目标数据,
* 初始对传入参数进行约束及避免无效计算的条件为,T<S[beginIndex]或T>S[endIndex]或beginIndex>endIndex
* 或beginIndex>S.length-1||endIndex>S.length-1||beginIndex<0||endIndex<0
*
*/
package junit.test;

public class BinarySearchTest {
/**
* 找到返回索引下标,否则返回-1;
* @return index
*/
public int binarySearch(int dataset[],int target,int beginIndex,int endIndex){
//数组校验
if(dataset==null||dataset.length==0){
return -1;
}
//beginIndex,endIndex校验
if(beginIndex>endIndex||beginIndex>dataset.length-1||endIndex>dataset.length-1||beginIndex<0||endIndex<0){
System.out.println("error arguments!");
return -1;
}

//无效参数处理
if(target<dataset[beginIndex]||target>dataset[endIndex]||beginIndex>endIndex){
return -1;
}
int midIndex=(beginIndex+endIndex)/2;

//System.out.println(midIndex);
if(target==dataset[midIndex]){
return midIndex;
}
else if(target<dataset[midIndex]){
return binarySearch(dataset,target,beginIndex,midIndex-1);//注意midIndex-1
}
else{
return binarySearch(dataset,target,midIndex+1,endIndex);//注意midIndex+1
}

}

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
BinarySearchTest bs=new BinarySearchTest();

int[] data=new int[]{1,3,5,7,9,12};

int index=bs.binarySearch(data,12,0, 5);

System.out.println("The position of the target number in the array is :"+ index);
}

}

后记:算法无穷妙,看来得好好学习下算法。

逐鹿IT, 猛猛如玉 wechat
扫一扫关注我,有惊喜不迷路
(转载本站文章请注明作者和出处: 逐鹿IT 猛猛如玉
网址: https://amonxu.com 微信公众号: itcraft
可以请我喝瓶水吗:)