Вдруг кому пригодится
| Код |
import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.Random;
import java.util.Set;
public class C001BinarySearch {
private static final int TEST_COUNT = 10000;
private static final int MAX_ARRAY_LENGTH = 500;
private static final int MAX_NUMBER_IN_ARRAY = 500;
public static void main(String[] args) {
for (int i = 0; i < TEST_COUNT; i++) {
run();
}
System.out.println(TEST_COUNT + " тестов завершено");
}
private static void run() {
Random r = new Random();
Set<Integer> sourceSet = new LinkedHashSet<>();
for (int i = 0, length = r.nextInt(MAX_ARRAY_LENGTH); i < length; i++) {
sourceSet.add(r.nextInt(MAX_NUMBER_IN_ARRAY));
}
if (sourceSet.size() < 2) {
return;
}
Integer[] source = sourceSet.toArray(new Integer[0]);
// System.out.println(Arrays.toString(source));
int elementToDel = source[new Random().nextInt(source.length)];
Integer[] output = new Integer[source.length - 1];
for (int i = 0, j = 0; i < source.length; i++) {
if (source[i] == elementToDel) {
continue;
}
output[j] = source[i];
j++;
}
// System.out.println(Arrays.toString(output));
int deletedElement = findDiffRecursion(source, output, 0,
source.length - 1);
if (deletedElement != elementToDel) {
System.out.println(Arrays.toString(source));
System.out.println(Arrays.toString(output));
System.out.println("Ошибка при нахождении " + elementToDel);
}
}
private static int findDiffRecursion(Integer[] source, Integer[] output,
int first, int last) {
if (last - first == 1) {
if (source[first] == output[first]) {
return source[last];
} else {
return source[first];
}
}
// вычисляем средний индекс, во избежание переполнения при очень
// больших числах, не используем (first + last) / 2
int i = first + (last - first) / 2;
// System.out.println("inside finder: [first=" + first + "], [i=" + i
// + "], [last=" + last + "]");
if (source[i] == output[i]) {
// если элементы равны, то смещение произошло правее
return findDiffRecursion(source, output, i, last);
} else {
// если не равны, то левее
return findDiffRecursion(source, output, first, i);
}
}
}
|
|
