Массив одна из самых популярных структур данных и в тоже время, самых старых. С их помощью можно решать многие задачи связанный с хранением, поиском, удалением и добавлением данных. В Java массив представляет собой ссылку на область память, где хранятся данные массива.
|
1 2 |
int [] a; //создали ссылку на массив a = new int[5]; //иницилизировали ссылку на массив |
Упорядоченный массив, представляет собой массив, в котором его элементы расположены в упорядоченном виде (по возрастанию/убыванию). Такие массивы используются в тех случаях, если при работе с ним, количество операций поиска элемента массива много больше операций вставок и удаления. Далее вы поймете почему.
И так, для поиска определенного элемента в массиве используют алгоритмы линейного и двоичного поиска. Рассмотрим каждый из них подробно для случая упорядоченного массива.
Алгоритм линейного поиска в упорядоченном массиве.
По сути алгоритм линейного поиска работает одинаково для упорядоченного и неупорядоченного массивов. Его суть заключается в последовательном переборе массива, начиная с первого(нулевого) элемента до тех пор, пока не будет найден нужный элемент. Стоит отметить, что этот алгоритм является эффективным для небольших массивов. Однако на практике в реальных прикладных программах такие случи довольно редки.
|
1 2 3 4 5 6 7 8 9 10 11 |
// Реализация алгоритма линейного поиска в упорядоченном массиве int[] array = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // иницилизация массива int el = 7; // элемент для поиска int count; // заводим счетчик for (count = 0; count < array.length; count++) { // проходим циклом по всему массиву if (array[count] == el) // проверяем, если элемент массива равен break; // искомому, то выходим из цикла } if (count == array.length) System.out.println("Element " + el + // если не нашли, то выводим на консоль сообщение " not found"); |
Заметим, что в среднем алгоритм работает за линейное время O(N).
Алгоритм двоичного поиска в упорядоченном массиве.
В отличии от линейного, алгоритм двоичного поиска эффективен только в упорядоченном массиве, однако скорость выполнения не так сильно зависит от размера массива. Даже можно сказать, что алгоритм двоичного поиска создан для поиска в массивах больших размеров.
Реализация алгоритма представляет собой известную игру “Угадай число”. Например, кто-то загадывает число от 0 до 100 (пусть будет 20), а вам нужно угадать число. Вы говорите 50, а в ответ слышите “меньше”, вы говорите “25”, ответ “меньше”, вы – “13” – “больше”, и т.д. пока не угадаете. Очевидно, что при каждой итерации мы уменьшаем выборку в два раза и так каждый раз. Мы выбираем среднее число между двумя концами и спрашиваем, больше оно или меньше искомого и исходя из ответа меняем концы выборки и повторяем.
|
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 |
// Реализация алгоритма двойного поиска в упорядоченном массиве int[] array = new int[100]; int leftBound = 0; int rightBound = array.length; for (int i = 0; i < 100; i++) array[i] = i + 1; int el = 49; int step = 1; while (true) { System.out.println("Step: " + step++); if (array[(rightBound + leftBound) / 2] == el) { System.out.println("Found " + el); break; } else if (rightBound == leftBound) { System.out.println("Found " + el); break; } else if (array[(rightBound + leftBound) / 2] < el) { leftBound = (rightBound + leftBound) / 2; } else if (array[(rightBound + leftBound) / 2] > el) { rightBound = (rightBound + leftBound) / 2; } } //////////////////////////////////////////////////////////////////// Step: 1 Step: 2 Step: 3 Step: 4 Step: 5 Step: 6 Found 49 |
В данном примере мы ищем число 49 в массиве из 100 элементов от 1 до 100. Обратим внимание на количество шагов, которые нам понадобились. 6 шагов двоичного поиска, против 48 шагов линейного имеем разницу в 6 раз!!! Алгоритм двоичного поиска работает в среднем O(log N).
P.S. В стандартной библиотеки Java (java.util.Arrays) есть метод двойного (бинарного) поиска:
|
1 |
java.util.Arrays.binarySearch(T[] array, T value[, Comparator c]) |
