Skip to content

Commit 25fea1b

Browse files
dunwudunwu
committed
🔖 查找算法示例
1 parent 77275d1 commit 25fea1b

File tree

5 files changed

+191
-0
lines changed

5 files changed

+191
-0
lines changed

‎codes/src/main/java/io/github/dunwu/algorithm/search/Search.java‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
package io.github.dunwu.algorithm.search;
2+
3+
/**
4+
* @author Zhang Peng
5+
*/
6+
public interface Search {
7+
/**
8+
* 排序接口
9+
* @param list 数组
10+
*/
11+
int search(int[] list, int key);
12+
}

‎codes/src/main/java/io/github/dunwu/algorithm/search/SearchStrategy.java‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package io.github.dunwu.algorithm.search;
2+
3+
import io.github.dunwu.algorithm.util.ArrayUtil;
4+
import org.slf4j.Logger;
5+
import org.slf4j.LoggerFactory;
6+
7+
/**
8+
* 使用策略模式，对算法进行包装
9+
* @author Zhang Peng
10+
*/
11+
public class SearchStrategy {
12+
private Search search;
13+
private static final Logger logger = LoggerFactory.getLogger(
14+
SearchStrategy.class);
15+
16+
public SearchStrategy(Search search) {
17+
this.search = search;
18+
}
19+
20+
public int search(int[] list, int key) {
21+
logger.info(this.search.getClass().getSimpleName() + " 查找开始：");
22+
logger.info("要查找的线性表：{}", ArrayUtil.getArrayString(list, 0, list.length - 1));
23+
logger.info("要查找的 key：{}", key);
24+
int index = this.search.search(list, key);
25+
logger.info("{} 的位置是：{}", key, index);
26+
return index;
27+
}
28+
}

‎codes/src/main/java/io/github/dunwu/algorithm/search/strategy/BinarySearch.java‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
package io.github.dunwu.algorithm.search.strategy;
2+
3+
import io.github.dunwu.algorithm.search.Search;
4+
5+
/**
6+
* @author Zhang Peng
7+
* @date 2018/4/18
8+
*/
9+
public class BinarySearch implements Search {
10+
11+
@Override
12+
public int search(int[] list, int key) {
13+
int low = 0, mid = 0, high = list.length - 1;
14+
while (low <= high) {
15+
mid = (low + high) / 2;
16+
if (list[mid] == key) {
17+
return mid; // 查找成功，直接返回位置
18+
} else if (list[mid] < key) {
19+
low = mid + 1; // 关键字大于中间位置的值，则在大值区间[mid+1, high]继续查找
20+
} else {
21+
high = mid - 1; // 关键字小于中间位置的值，则在小值区间[low, mid-1]继续查找
22+
}
23+
}
24+
return -1;
25+
}
26+
}

‎codes/src/main/java/io/github/dunwu/algorithm/search/strategy/OrderSearch.java‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
package io.github.dunwu.algorithm.search.strategy;
2+
3+
import io.github.dunwu.algorithm.search.Search;
4+
5+
/**
6+
* @author Zhang Peng
7+
* @date 2018/4/18
8+
*/
9+
public class OrderSearch implements Search {
10+
11+
@Override
12+
public int search(int[] list, int key) {
13+
// 从前往后扫描list数组，如果有元素的值与key相等，直接返回其位置
14+
for (int i = 0; i < list.length; i++) {
15+
if (key == list[i]) {
16+
return i;
17+
}
18+
}
19+
20+
// 如果扫描完，说明没有元素的值匹配key，返回-1，表示查找失败
21+
return -1;
22+
}
23+
}

‎codes/src/test/java/io/github/dunwu/algorithm/search/SearchStrategyTest.java‎

Lines changed: 102 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,102 @@
1+
package io.github.dunwu.algorithm.search;
2+
3+
import io.github.dunwu.algorithm.search.strategy.BinarySearch;
4+
import io.github.dunwu.algorithm.search.strategy.OrderSearch;
5+
import io.github.dunwu.algorithm.util.ArrayUtil;
6+
import java.util.Arrays;
7+
import java.util.Random;
8+
import org.junit.Assert;
9+
import org.junit.Before;
10+
import org.junit.BeforeClass;
11+
import org.junit.FixMethodOrder;
12+
import org.junit.Test;
13+
import org.junit.runners.MethodSorters;
14+
15+
/**
16+
* 排序算法单元测试
17+
* 如果需要打印每趟排序的结果，可以修改 logback.xml 中
18+
* <logger name="io.github.dunwu" level="INFO" additivity="false"> 的 level 级别，改为 DEBUG，
19+
* 日志就会打印 debug 信息。
20+
*
21+
* @author Zhang Peng
22+
*/
23+
@FixMethodOrder(MethodSorters.NAME_ASCENDING)
24+
public class SearchStrategyTest {
25+
26+
/**
27+
* 随机样本一
28+
*/
29+
private static int[] origin01;
30+
private static int target01;
31+
private static int expected01;
32+
33+
/**
34+
* 随机样本二
35+
*/
36+
private static int[] origin02;
37+
private static int target02;
38+
private static int expected02;
39+
40+
/**
41+
* 随机样本三
42+
*/
43+
private static int[] origin03;
44+
private static int target03;
45+
private static int expected03;
46+
47+
/**
48+
* 生成随机数组样本，并调用 JDK api 生成期望的有序数组
49+
*/
50+
@BeforeClass
51+
public static void beforeClass() {
52+
Random random = new Random();
53+
54+
// 在 [0, 100] 间生成长度为 10 的存在重复的随机数组
55+
origin01 = ArrayUtil.randomRepeatArray(0, 10, 9);
56+
expected01 = random.nextInt(origin01.length);
57+
58+
// 在 [0, 100] 间生成长度为 17 的不重复的随机数组
59+
origin02 = ArrayUtil.randomNoRepeatArray(0, 100, 17);
60+
expected02 = random.nextInt(origin02.length);
61+
62+
// 在 [0, 100] 间生成长度为 100 的不重复的随机数组
63+
origin03 = ArrayUtil.randomNoRepeatArray(0, 100, 100);
64+
expected03 = random.nextInt(origin03.length);
65+
}
66+
67+
/**
68+
* 每次执行 @Test 前都使用生成的随机样本初始化实际用于排序的数组
69+
*/
70+
@Before
71+
public void before() {
72+
}
73+
74+
/**
75+
* 如果查找的是重复集，可能会出现断言
76+
*/
77+
@Test
78+
public void testOrderSearch() {
79+
SearchStrategy strategy = new SearchStrategy(new OrderSearch());
80+
executeSearch(strategy);
81+
}
82+
83+
@Test
84+
public void testBinarySearch() {
85+
SearchStrategy strategy = new SearchStrategy(new BinarySearch());
86+
executeSearch(strategy);
87+
}
88+
89+
/**
90+
* 注入 BinarySearch，执行对三个样本的排序测试
91+
*/
92+
private void executeSearch(SearchStrategy strategy) {
93+
int target01 = strategy.search(origin01, origin01[expected01]);
94+
Assert.assertEquals(expected01, target01);
95+
96+
int target02 = strategy.search(origin02, origin02[expected02]);
97+
Assert.assertEquals(expected02, target02);
98+
99+
int target03 = strategy.search(origin03, origin03[expected03]);
100+
Assert.assertEquals(expected03, target03);
101+
}
102+
}

0 commit comments

Comments
 (0)