Търсене на интерполация в Java

1. Въведение

В този урок ще разгледаме алгоритмите за търсене на интерполация и ще обсъдим техните плюсове и минуси. Освен това ще го внедрим в Java и ще говорим за сложността на времето на алгоритъма.

2. Мотивация

Интерполационното търсене е подобрение спрямо бинарното търсене, съобразено с равномерно разпределени данни.

Двоичното търсене намалява наполовина пространството за търсене на всяка стъпка, независимо от разпределението на данните, поради което сложността на времето винаги е O (log (n)) .

От друга страна, сложността на времето за интерполационно търсене варира в зависимост от разпределението на данните . Това е по-бързо от бинарното търсене на равномерно разпределени данни с времевата сложност на O (log (log (n))) . В най-лошия случай обаче може да се представи толкова лошо, колкото O (n) .

3. Търсене на интерполация

Подобно на двоичното търсене, търсенето с интерполация може да работи само върху сортиран масив. Той поставя сонда в изчислено положение на всяка итерация. Ако сондата е точно върху търсения артикул, позицията ще бъде върната; в противен случай пространството за търсене ще бъде ограничено или от дясната, или от лявата страна на сондата.

Изчисляването на позицията на сондата е единствената разлика между двоичното търсене и търсенето с интерполация.

При двоично търсене позицията на сондата винаги е най-средният елемент от оставащото пространство за търсене.

Напротив, интерполационното търсене изчислява позицията на сондата въз основа на тази формула:

Нека да разгледаме всеки от термините:

  • сонда : новата позиция на сондата ще бъде присвоена на този параметър.
  • lowEnd : индексът на най-левия елемент в текущото пространство за търсене.
  • highEnd : индексът на най-десния елемент в текущото пространство за търсене.
  • data [] : масивът, съдържащ оригиналното пространство за търсене.
  • артикул : артикулът, който търсим.

За да разберем по-добре как работи търсенето с интерполация, нека го демонстрираме с пример.

Да кажем, че искаме да намерим позицията на 84 в масива по-долу:

Дължината на масива е 8, така че първоначално highEnd = 7 и lowEnd = 0 (тъй като индексът на масива започва от 0, а не от 1).

В първата стъпка формулата на позицията на сондата ще доведе до сонда = 5:

Тъй като 84 ( елементът, който търсим) е по-голям от 73 (текущият елемент на позицията на сондата ), следващата стъпка ще изостави лявата страна на масива, като присвои lowEnd = probe + 1. Сега пространството за търсене се състои само от 84 и 101. Формулата за позицията на сондата ще зададе sonde = 6, което е точно индексът на 84:

Тъй като търсеният артикул е намерен, позиция 6 ще бъде върната.

4. Внедряване в Java

Сега, след като разбрахме как работи алгоритъмът, нека го внедрим в Java.

Първо инициализираме lowEnd и highEnd :

int highEnd = (data.length - 1); int lowEnd = 0;

След това настройваме цикъл и във всяка итерация изчисляваме новата сонда въз основа на гореспоменатата формула. Условието на цикъла гарантира, че не сме извън пространството за търсене, като сравняваме елемент с данни [lowEnd] и данни [highEnd] :

while (item >= data[lowEnd] && item <= data[highEnd] && lowEnd <= highEnd) { int probe = lowEnd + (highEnd - lowEnd) * (item - data[lowEnd]) / (data[highEnd] - data[lowEnd]); }

Също така проверяваме дали сме намерили елемента след всяко ново задание на сондата .

И накрая, ние коригираме lowEnd или highEnd, за да намалим пространството за търсене на всяка итерация:

public int interpolationSearch(int[] data, int item) { int highEnd = (data.length - 1); int lowEnd = 0; while (item >= data[lowEnd] && item <= data[highEnd] && lowEnd <= highEnd) { int probe = lowEnd + (highEnd - lowEnd) * (item - data[lowEnd]) / (data[highEnd] - data[lowEnd]); if (highEnd == lowEnd) { if (data[lowEnd] == item) { return lowEnd; } else { return -1; } } if (data[probe] == item) { return probe; } if (data[probe] < item) { lowEnd = probe + 1; } else { highEnd = probe - 1; } } return -1; }

5. Заключение

В тази статия разгледахме търсенето на интерполация с пример. Ние го внедрихме и в Java.

Примерите, показани в този урок, са достъпни в Github.