package src.MyTests.BinarySearch;
import java.util.Arrays;
public class BinarySearchWithRecursion {
public static void main(String[] args) {
int[] array = new int[100000000];
int key = 99999999;
arrayRandomFill(array);
long time1 = System.currentTimeMillis();
enumerationMethod(array, key);
System.out.println("1 enumerationMethod time: " + (System.currentTimeMillis() - time1));
long time2 = System.currentTimeMillis();
binarySearchRecursion(array, key);
System.out.println("2 binarySearch time: " + (System.currentTimeMillis() - time2));
}
public static int[] arrayRandomFill(int[] array) {
for (int i = 0; i < array.length; i++) {
array[i] = i;
}
return array;
}
public static int enumerationMethod(int[] array, int key) {
for (int i = 0; i < array.length; i++) {
if (array[i] == key) return i;
}
return -1;
}
public static int binarySearchRecursion(int[] array, int key) {
return binarySearchRecursion(array, 0, array.length, key);
}
public static int binarySearchRecursion(int[] array, int start, int end, int key) {
Arrays.sort(array);
int mid = (start + end) / 2;
if (key == array[mid]) return mid;
else if (key < array[mid]) return binarySearchRecursion(array, 0, mid - 1, key);
else if (key > array[mid]) return binarySearchRecursion(array, mid + 1, array.length - 1, key);
else return -1;
}
}
Андрей Столяров
34 уровень
Почему бинарный поиск медленнее чем линейный?
Решен
Комментарии (6)
- популярные
- новые
- старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
Андрей Столяров
6 октября 2022, 13:47
Написал программу, которая заполняет массив числами от 0 до 99999999, ищет число, которое находится в последней ячейке и выводит в консоль время, которое понадобится для поиска числа через линейный поиск и бинарный. Почему линейный всегда выигрывает если для поиска ему понадобится 99999999 циклов, а для бинарного 27. Где я мог ошибиться?
0
Михаил
6 октября 2022, 14:19
не знаю, но могу порассуждать:
перебор очень хорошо ложиться на современные процессоры которые предсказывают и параллелят выполнение.Предсказатель переходов В бинарном же поиске ты используешь процессор в строго линейном направлении вызываешь рекурсию (вроде бы наращивая стек) и заставляя процессор заново считать.
0
Ant
6 октября 2022, 14:21решение
думаю проблема просто в Arrays.sort(array);, и ещё это все в рекурсии.
+2
Михаил
6 октября 2022, 14:29полезный
ты прав, только я закомментировал Arrays.sort(array) то сразу стало
1 enumerationMethod time: 36
2 binarySearch time: 0
+2
Андрей Столяров
6 октября 2022, 14:47
Спасибо! Правда помогло. Просто изначально писал, что весь массив заполнится рандомными элементами, для этого там и был сорт
0
Андрей Столяров
6 октября 2022, 14:47
Спасибо!
0