Един от най-фундаменталните алгоритми в компютърните науки е алгоритъмът за двоично търсене. Можете да реализирате двоично търсене, като използвате два метода: итеративния метод и рекурсивния метод. Въпреки че и двата метода имат еднаква времева сложност, итеративният метод е много по-ефективен по отношение на пространствената сложност.

Итеративният метод има пространствена сложност от О(1) в сравнение с O(вход) произведени по рекурсивен метод. И така, как можете да приложите алгоритъма за двоично търсене, като използвате итеративния метод в C, C++ и Python?

Какво е двоично търсене?

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

Ако елементът за търсене е по-голям от средния елемент, това означава, че всички елементи от лявата страна са по-малки от елемента за търсене. И така, контролът се измества в дясната страна на масива (ако масивът е във възходящ ред), като увеличава долната граница до следващата позиция на средния елемент.

instagram viewer

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

Това драстично намалява броя на сравненията в сравнение с изпълнение на линейно търсене където броят на сравненията е равен на броя на елементите в най-лошия сценарий. Този метод се оказва много полезен за намиране на номера в телефонен указател или думи в речник.

Ето диаграмно представяне на Алгоритъм за двоично търсене:

Двоично търсене с помощта на C

Следвайте тези стъпки, за да приложите двоично търсене с помощта на C:

Целият изходен код на програмата за двоично търсене, използваща C, C++, Java и Python, присъства в това GitHub хранилище.

Програмата дефинира функция, binarySearch(), който връща или индекса на намерената стойност, или -1 ако не е налице:

#включи <stdio.h>
вътрдвоично търсене(вътр пристигане [], вътр arr_size, вътр търсене_номер){
/*... */
}

Функцията работи чрез итеративно стесняване на пространството за търсене. Тъй като двоичното търсене работи върху сортирани масиви, можете да изчислите средата, което иначе няма смисъл. Можете или да поискате от потребителя сортиран масив, или да използвате алгоритми за сортиране като Bubble или Selection sort.

The ниско и Високо променливите съхраняват индексите, които представляват границите на текущото пространство за търсене. средата съхранява индекса в средата:

вътр ниско = 0, високо = arr_size - 1, средата;

Основното докато() цикъл ще стесни пространството за търсене. Ако стойността на ниския индекс някога стане по-голяма от високия индекс, тогава пространството за търсене е изчерпано, така че стойността не може да присъства.

докато (ниско <= високо) {
/* продължава... [1] */
 }
връщане-1;

След актуализиране на средната точка в началото на цикъла има три възможни резултата:

  1. Ако стойността в средната точка е тази, която търсим, върнете този индекс.
  2. Ако средната стойност е по-голяма от тази, която търсим, намалете високата.
  3. Ако средната стойност е по-малка, увеличете ниската. 
/* [1] ...продължение */
 среден = (нисък + (висок - нисък)) / 2;
if (arr[mid] == search_number)
връщане среден;
другоако (arr[mid] > search_number)
 висок = среден - 1;
друго
 ниско = средно + 1;

Тествайте функцията с въвеждане от потребителя. Използвайте scanf() за да получите вход от командния ред, включително размера на масива, неговото съдържание и число за търсене:

вътросновен(){
вътр пристигане [100], i, arr_size, search_number;
 printf("Въведете брой елементи: ");
 scanf("%д", &arr_size);
 printf("Моля, въведете числа: ");
за (i = 0; аз < arr_size; i++) {
 scanf("%д", &arr[i]);
 }


printf("Въведете номер за търсене: ");
 scanf("%д", &търсене_номер);


i = binarySearch (arr, arr_size, search_number);


ако (i==-1)
 printf("Номерът не присъства");
друго
 printf("Номерът присъства на позиция %d", i + 1);
връщане0;
}

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

Двоично търсене с помощта на C++

Можете да конвертирате C програмата в C++ програма, като импортирате Входен изходен поток и използва пространство от имена std за да избегнете повтарянето му многократно по време на програмата.

#включи <iostream>
използвайки пространство от именаstd;

Използвайте cout с екстракционен оператор << вместо printf() и цин с оператор за вмъкване >> вместо scanf() и вашата C++ програма е готова.

printf("Въведете брой елементи: ");
cout <<"Въведете брой елементи: ";
scanf("%д", &arr_size);
цин >> arr_size;

Двоично търсене с помощта на Python

Тъй като Python няма вградена поддръжка за масиви, използвайте списъци. Дефинирайте функция, binarySearch(), който приема три параметъра, списъка, неговия размер и номер за търсене:

дефдвоично търсене(arr, arr_size, search_number):
 ниско = 0
 високо = arr_size - 1
докато ниско <= високо:
 среден = нисък + (високо-ниско)//2
 if arr[mid] == search_number:
връщане средата
елиф arr[mid] > search_number:
 високо = средно - 1
друго:
 ниско = средно + 1
връщане-1

Инициализирайте две променливи, ниско и Високо, за да служи като долна и горна граница на списъка. Подобно на изпълнението на C, използвайте a докато цикъл, който стеснява пространството за търсене. Инициализиране средата за съхраняване на средната стойност на списъка. Python предоставя оператора за разделяне на етажа (//), който предоставя възможно най-голямото цяло число.

Направете сравнения и стеснете пространството за търсене, докато средната стойност се изравни с търсеното число. Ако номерът за търсене не присъства, контролата ще се върне -1.

arr_size = int (вход("Въведете брой елементи: "))
пристигане=[]
печат ("Моля, въведете числа: ", край="")
за i в диапазон (0,arr_size):
 arr.append(вътр(вход()))
номер_за_търсене = int (вход("Въведете номер за търсене: "))
резултат = binarySearch (arr, arr_size, search_number)
ако резултат == -1:
 печат ("Номерът не присъства")
друго:
 print("Число е присъства на позиция ", (резултат + 1))

Тествайте функцията с въвеждане от потребителя. Използвайте вход() за да получите размера на списъка, неговото съдържание и номер за търсене. Използвайте int() за типизиране на входния низ, приет от Python по подразбиране, в цяло число. За да добавите номера към списъка, използвайте добавям () функция.

Обадете се binarySearch() и предайте аргументите. Ако намерите номера, покажете неговата позиция или индекс, в противен случай съобщение, че номерът не присъства.

Резултат от алгоритъма за двоично търсене

Следното е резултатът от алгоритъма за двоично търсене, когато елементът присъства в масива:

Следното е резултатът от алгоритъма за двоично търсене, когато елементът не присъства в масива:

Научете основните структури на данни и алгоритми

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

Освен това е от съществено значение да се разбере времевата и пространствената сложност на алгоритмите. Те са една от най-важните концепции в компютърните науки при определяне на ефективността на всеки алгоритъм. С познания по структури от данни и алгоритми, вие сте длъжни да създавате най-добрите програми.