Алгоритми за двоично търсене, обяснени с помощта на C ++

Двоичното търсене е един от онези алгоритми, които ще срещнете при всеки (добър) уводен час по компютърни науки. Това е ефективен алгоритъм за намиране на елемент в подреден списък. Заради този пример просто ще приемем, че това е масив.

Целите на двоичното търсене са:

  • да може да отхвърля половината от масива при всяка итерация
  • минимизирайте броя на елементите, през които трябва да преминем
  • оставете ни с една крайна стойност

Вземете например следния масив от цели числа:

int array[] = { 1, 3, 4, 6, 7, 8, 10, 13, 14, 18, 19, 21, 24, 37, 40, 45, 71 };

Да кажем, че се опитваме да намерим стойността на индекса на числото 7 в този масив. Общо има 17 елемента и стойностите на индекса се движат от 0 до 16.

Виждаме, че стойността на индекса 7 е 4, тъй като това е петият елемент в масива.

Но какъв би бил най-добрият начин компютърът да намери стойността на индекса на числото, което търсим?

Първо, ние съхранява minи maxценности, като 0и 16.

int min = 0;int max = 16;

Сега трябва да измислим предположение. Най-умното нещо, което трябва да направите, би било да отгатнете стойност на индекс в средата на масива.

Със стойността на индекса от 0 до 16 в този масив средната стойност на индекса на този масив ще бъде 8. Това съдържа числото 14.

// This will round down if the quotient is not an integer

int guess = (min + max) / 2;

Нашето предположение сега е равно на 8, което е 14 в масива, тъй като array[8]е равно на 14.

Ако търсеният от нас номер беше 14, щяхме да свършим!

Тъй като това не е така, сега ще изхвърлим половината от масива. Това са всички числа след 14 или стойност на индекса 8, тъй като знаем, че 14 е по-голямо от 7 и нашето предположение е твърде високо.

След първата итерация, нашето търсене вече е в: 1, 3, 4, 6, 7, 8, 10, 13

Не е нужно да гадаем в последната половина на оригиналния масив, защото знаем, че всички тези стойности са твърде големи. Ето защо е важно да приложим двоично търсене към подреден списък.

Тъй като първоначалното ни предположение за 14 беше по-голямо от 7, сега го намаляваме с 1 и съхраняваме това в max:

max = guess - 1; // max is now equal to 7, which is 13 in the array

Сега търсенето изглежда така:

 1, 3, 4, 6, 7, 8, 10, 13
min = 0max = 7guess = 3 

Тъй като нашето предположение беше твърде ниско, ние изхвърляме долната половина на масива, като увеличаваме min, обратно на това, което направихме преди max:

min = guess + 1; // min is now 4

До следващата итерация ни остава:

 7, 8, 10, 13min = 4max = 7guess = 5

Тъй като стойността на индекса 5 връща 8, сега сме едно над целта си. Повтаряме процеса отново и ни остава:

 7min = 4max = 4guess = 4

И ни остава само една стойност, 4, като индекс на целевото число, което търсихме, което беше 7.

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

Псевдокодът за този алгоритъм ще изглежда по следния начин:

  1. Нека min = 0и нека max = nкъде nе възможно най-високата стойност на индекса
  2. Намерете средната стойност на minи max, закръглете надолу, така че да е цяло число. Това е нашеguess
  3. Ако познахме номера, спрете, разбрахме!
  4. Ако guessе твърде ниско, задайте minравно на едно повече отguess
  5. Ако guessе твърде високо, задайте maxравно на едно по-малко отguess
  6. Върнете се към стъпка две.

Ето решение, написано на C ++: