Вступление

Будь то поиск в плейлисте с любимой песней или поиск в каталоге, чтобы выбрать ресторан, в котором вы будете в следующий раз пообедать, наша жизнь наполнена поиском вещей.

Точно так же компьютеры выполняют поисковые запросы по своим коллекциям и структурам данных. Однако, в отличие от людей, компьютеры должны выполнять поиск в гораздо более крупных наборах данных в разы быстрее, чем люди.

Это побудило компьютерных ученых придумать множество алгоритмов поиска, каждый из которых обычно более оптимален, чем другие, для определенных коллекций.

Перейти к поиску

Поиск с переходом (также называемый поиском по блоку ) - это алгоритм, используемый для поиска позиции целевого элемента в отсортированном наборе или структуре данных.

Вместо поиска в массиве поэлементно (линейный поиск) - Jump Search оценивает блоки элементов. Вернее, поскольку это отсортированный массив - элемент с наибольшим значением в каждом блоке.

Если значение меньше целевого элемента, рассматривается следующий блок.
Если значение выше целевого элемента, целевой элемент находится в текущем блоке.
Если значение является целевым элементом - просто верните его.

Итеративно сдвигая, или, скорее, прыгая вперед, мы либо найдем целевой элемент, либо достигнем конца коллекции, не найдя его.

Вот визуальное представление о том, как работает Jump Search:

{.ezlazyload}

Очевидно, что Jump Search всегда ищет вперед по своим массивам, в отличие от методов прямого и обратного поиска, таких как двоичный поиск. Такое поведение делает Jump Search намного более эффективным для поиска данных, хранящихся на физических дисках с вращающимися носителями.

Кроме того, другой способ понять этот поиск - без блоков - есть просто разрыв между оцениваемыми элементами. Во время выполнения алгоритма в памяти не сохраняется никаких реальных блоков.

Выполнение

При этом давайте реализуем Jump Search. Есть два подхода, которые вы можете использовать, без реального «победителя» между ними - итеративная и рекурсивная реализация.

Выбор между этими двумя вариантами зависит от вас, и если вы не работаете с безумно огромными наборами данных, разницы в производительности быть не должно. Рекурсия приводит к более высокому использованию пространства процессора / памяти, но обычно более удобна для чтения и записи.

Опять же, если вы работаете с действительно большими наборами данных, вы, вероятно, использовали бы более эффективные, оптимизированные алгоритмы поиска.

Итеративная реализация

При этом давайте начнем с итеративного подхода:

 public static int jumpSearch(int[] arrayToSearch, int element) { 
 int blockSize = (int) Math.floor(Math.sqrt(arrayToSearch.length)); 
 
 int currentLastIndex = blockSize-1; 
 
 // Jump to next block as long as target element is > currentLastIndex 
 // and the array end has not been reached 
 while (currentLastIndex < arrayToSearch.length && element > arrayToSearch[currentLastIndex]) { 
 currentLastIndex += blockSize; 
 } 
 
 // Find accurate position of target element using Linear Search 
 for (int currentSearchIndex = currentLastIndex - blockSize + 1; 
 currentSearchIndex <= currentLastIndex && currentSearchIndex < arrayToSearch.length; currentSearchIndex++) { 
 if (element == arrayToSearch[currentSearchIndex]) { 
 return currentSearchIndex; 
 } 
 } 
 // Target element not found. Return negative integer as element position. 
 return -1; 
 } 

Во-первых, мы рассчитали размер блока. Как правило, лучше выбирать квадратный корень из длины массива. Это более подробно объясняется в разделе « Анализ большого вопроса». Поиск в таком блоке, в конце концов, также будет дешевым для такого алгоритма, как линейный поиск.

Поскольку массив отсортирован, если значение нашего целевого элемента больше, чем значение текущего элемента, то целевой элемент определенно не может находиться внутри текущего блока. Итак, мы переходим к следующему блоку и сравниваем целевой элемент со значением последнего индексного элемента нового блока.

Этот переход повторяется до тех пор, пока не будет найден блок, содержащий целевой элемент.

Если целевой элемент больше не превышает значение последнего элемента в блоке, то он должен находиться внутри блока, если он вообще существует.

Таким образом, мы найдем точное положение целевого элемента с помощью линейного поиска.

Если мы дойдем до конца массива, не найдя блок, содержащий наш целевой элемент - его нет в массиве, и мы возвращаем -1 чтобы обозначить это.

Рекурсивная реализация

Разобравшись с итеративной реализацией, давайте также рассмотрим рекурсивную реализацию:

 public static int jumpSearchInit(int[] arrayToSearch, int element) { 
 int blockSize = (int) Math.sqrt(arrayToSearch.length); 
 
 // Hold the last index of the current block 
 int currentLastIndex = blockSize-1; 
 
 return jumpSearch(arrayToSearch, element, blockSize, currentLastIndex); 
 } 
 
 public static int jumpSearch(int[] arrayToSearch, int element, int blockSize, int currentLastIndex) { 
 if (currentLastIndex < arrayToSearch.length && element > arrayToSearch[currentLastIndex]) { 
 currentLastIndex += blockSize; 
 // Make recursive call to jumpSearch method 
 return jumpSearch(arrayToSearch, element, blockSize, currentLastIndex); 
 } else { 
 // Find accurate position of target element using linear search 
 for (int currentSearchIndex = currentLastIndex - blockSize + 1;currentSearchIndex <= currentLastIndex && currentSearchIndex < arrayToSearch.length; currentSearchIndex++) { 
 if (element == arrayToSearch[currentSearchIndex]) { 
 return currentSearchIndex; 
 } 
 } 
 } 
 // Target element not found. Return negative integer as element position. 
 return -1; 
 } 

Рекурсивное выполнение Jump Search работает точно так же. Мы просто вызываем метод рекурсивно вместо того , чтобы иметь while цикл.

Нам нужно использовать метод инициализатора для выполнения некоторых начальных вычислений. А именно оптимальный размер блока и последний индекс самого первого блока.

После этого, пока наш целевой элемент больше, чем значение последнего элемента индекса текущего блока, мы рекурсивно вызываем метод Jump Search, передавая ему параметры следующего блока.

Эта рекурсия заканчивается после того, как был найден блок, содержащий целевой элемент, или если в конце концов был достигнут конец массива.

В случае, если такой целевой блок был найден, мы выполняем линейный поиск по нему, чтобы найти положение целевого элемента.

Сравнительный анализ Jump Search

Давайте протестируем Jump Search, запустив его для отсортированных целочисленных массивов различного размера. Конечно, мы будем искать наихудший сценарий во всех этих случаях (последний элемент):

Размер массива 1-й прогон (мс) 2-й прогон (мс) 3-й прогон (мс) Среднее (мс) 10 0,3595 0,2267 0,3477 0,3119 10 000 0,2210 0,5809 0,2225 0,3410 1,000,000 0,7754 0,7788 0,7906 0,7816

По сравнению с линейным поиском, который занимает 5,4209 мс , очевидно, что поиск Jump Search значительно быстрее.

Анализ Big-O

Рассмотрим отсортированный целочисленный массив размера n с размером блока m .

В лучшем случае Jump Search найдет целевой элемент на краю самого первого блока, в котором он выполняет поиск. В свою очередь, это приводит к тому, что Jump Search имеет эффективность O (1) сложности в терминах Big-O Notation. .

Напротив, в худшем случае Jump Search будет последовательно переходить к самому последнему блоку в поисках целевого элемента, в свою очередь вызывая количество переходов n/m Кроме того, если значение последнего элемента этого блока было больше целевого элемента, Jump Search будет выполнять линейный поиск с m-1 итерациями.

Это заставляет Jump Search делать (n/m) прыжков с дополнительными m-1 итерациями. Это значение минимально при m = √n . Следовательно, оптимальный размер блока составляет √n .

Соответственно, Jump Search поддерживает эффективность наихудшего и среднего случая сложности O (√n) .

Это заставляет отметить, что, хотя Jump Search очень эффективен для поиска в массивах, особенно когда его поведение с поиском вперед является благоприятным, его средняя производительность заставляет его находиться где-то между двоичным поиском с его сложностью O (log n) и линейным поиском с сложность O (n).

Кроме того, Jump Search постоянно требует, чтобы массивы, в которых выполнялся поиск, были заранее отсортированы в порядке возрастания.

Заключение

Поиск Jump Search выполняется путем поблочного перехода вперед по массиву до тех пор, пока не будет найден блок, который может содержать данный элемент.

В этой статье мы реализовали итеративный и рекурсивный поиск Jump Search и протестировали алгоритм с массивами разного размера.

Кроме того, мы провели анализ Big-O, доказывающий, как Jump Search приобрел среднюю и худшую эффективность O (√n) .