Продолжаю просмотр лекций курса «Introduction to Algorithms» MIT: http://videolectures.net/mit6046jf05_demaine_lec03/
В результате решил для тренировки реализовать двоичный поиск. Бинарный поиск, как известно, предназначен для поиска данных в отсортированном массиве. Суть алгоритма заключается в проверке значений на границах массива. Затем в цикле берется индекс середины массива, сравнивается значение хранящееся в среднем элементе массива с искомым. Если искомое значение равно среднему элементу, значит элемент найден. Если нет, то в зависимости от результата сравнения искомого значения со значением среднего элемента берется либо младшая половина либо старшая половина массива и с ней повторяется процедура проверки среднего элемента. Так до тех пор, пока поиск либо завершится успехом, либо поиск будет не успешен.
С нуля, впрочем, даже такой казалось бы простой, алгоритм писать смысла нет. Для начала надо поискать готовое решение. Готовое решение находится здесь: http://ru.wikipedia.org/wiki/Двоичный поиск.
Портирую код в Java. Получаю такой код:
public class BinarySearch<T> {
public static class Result {
public final boolean success;
public final int index;
public Result(boolean success, int index) {
this.success = success;
this.index = index;
}
}
public static <T> Result search(T[] objects, int first, int last, T x, Comparator<? super T> comparator) {
if(objects.length < last) {
last = objects.length;
}
if (last == 0) {
// not found, if you need to insert the element then in position 0
return new Result(false, 0);
}
int cmp = comparator.compare(objects[first], x);
if (cmp > 0) {
// not found, if you need to insert the element then in first position
return new Result(false, first);
} else if(cmp == 0) {
return new Result(true, first);
}
cmp = comparator.compare(objects[last - 1],x);
if (cmp < 0) {
// not found, if you need to insert element then in last position
return new Result(false, last);
} else if (cmp == 0) {
return new Result(true, last-1);
}
while (first < last) {
int mid = first + (last - first) / 2;
cmp = comparator.compare(x, objects[mid]);
if (cmp < 0) {
last = mid;
} else if (cmp == 0) {
return new Result(true, mid);
} else {
first = mid + 1;
}
}
if (comparator.compare(objects[last], x) == 0) {
return new Result(true, last);
} else {
// Not found, if you need to insert the element then it's place - last
return new Result(false, last);
}
}
}
Метод search в качестве параметров принимает массив объектов, диапозон индексов, внутри которого нужно делать поиск (в случае, если поиск осуществляется не по всему, а по части массива). Четвертый параметр — искомый объект. Пятый — класс Comparator, реализующий сравнение двух объектов. Параметров слишком много, их порядок не слишком удобно запоминать. Поэтому делаю дополнительные методы:
T[] objects;
Comparator<? super T> comparator;
private int first;
private int last;
public BinarySearch<T> in(T[] objects) {
this.objects = objects;
this.first = 0;
this.last = objects.length;
return this;
}
public BinarySearch<T> range(int first, int size) {
this.first = first;
this.last = size;
return this;
}
public BinarySearch<T> comparator(Comparator<? super T> comparator) {
this.comparator = comparator;
return this;
}
public Result search(T x) {
return search(objects, first, last, x, comparator);
}
Эти методы позволяют улучшить читаемость кода. Ниже юнит-тесты:
@Test
public void testSuccessSearch() {
Integer[] a = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
BinarySearch<Integer> search = new BinarySearch<Integer>()
.in(a).comparator(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
});
for(int i=0; i<a.length; i++) {
BinarySearch.Result result = search.search(i);
assertTrue(result.success);
assertEquals(result.index, i);
}
}
@Test
public void testSuccessSearchOddArraySize() {
Integer[] a = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };
BinarySearch<Integer> search = new BinarySearch<Integer>()
.in(a).comparator(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
});
for(int i=0; i<a.length; i++) {
BinarySearch.Result result = search.search(i);
assertTrue(result.success);
assertEquals(result.index, i);
}
}
@Test
public void testForFails() {
Integer[] a = { 0, 1, 2, 3, 4, 5, 6, 7, 10, 11, 12, 13 };
BinarySearch<Integer> search = new BinarySearch<Integer>()
.in(a).comparator(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
});
BinarySearch.Result result = search.search(-1);
assertTrue(!result.success);
assertEquals(result.index, 0);
result = search.search(8);
assertTrue(!result.success);
assertEquals(result.index, 8);
result = search.search(9);
assertTrue(!result.success);
assertEquals(result.index, 8);
result = search.search(100500);
assertTrue(!result.success);
assertEquals(result.index, a.length);
}
Юнит-тесты позволяют проверить отсутствие ошибок. А также, что интересно, они позволяют оптимизировать слегка код. Для этого подключаю к проекту Cobertura:
добавляю в pom.xml секцию build:
<build>
<plugins>
<plugin>
<groupId>org.codehaus.mojo</groupId>
<artifactId>cobertura-maven-plugin</artifactId>
<executions>
<execution>
<id>site</id>
<phase>pre-site</phase>
<goals>
<goal>cobertura</goal>
</goals>
</execution>
</executions>
</plugin>
</plugins>
</build>
и добавляю в конец pom.xml секцию reporting:
<reporting>
<plugins>
<plugin>
<groupId>org.codehaus.mojo</groupId>
<artifactId>cobertura-maven-plugin</artifactId>
<version>2.5.2</version>
</plugin>
</plugins>
</reporting>
Создаю отчет, стартовав maven командой: maven clean site
Получаю отчет и в каталоге target/site получаю отчет. Нахожу в нем покрытие моего класса тестами. Нахожу вот что.
Зеленым цветом помечены протестированные строки. Цифрочки указывают количество раз, которое данная строка выполнилась. Красным показываются строки, в которые код из-за выполнения тех или иных условий не попал. Что тут видно. Видно, что я не протестировал что мой код вернет в случае пустого массива, не протестировал что вернется в случае если диапозон поиска будет указан за границами массива и, наконец, нашел, что условие в 86 строчке всегда возвращает false. Поэтому условие можно выбросить за ненадобностью.
Выводы…
Во-первых, Cobertura — замечательное средство для анализа кода.
Во-вторых, юнит-тестирование полезная вещь.
В третьих, не факт, что код из wiki: http://ru.wikipedia.org/wiki/Двоичный поиск будет работать. Хотя идея в нем в целом показана прекрасно, и замечания тоже весьма полезные. Однако свой код, написанный на основе кода из упомянутой статьи все равно стоит «вдоль и поперек» протестировать.
dev64 