introduction searching algorithms c
Prehľad vyhľadávania algoritmov v jazyku C ++.
Stále hľadáme niečo alebo iné v každodennom živote. Rovnako ako náš každodenný život, aj my ako softvéroví profesionáli musíme hľadať informácie na našom počítači. Vyhľadávanie informácií by malo prebiehať rýchlo, pretože si nemôžeme dovoliť strácať veľa času hľadaním informácií.
Preto potrebujeme niekoľko efektívnych vyhľadávacích techník alebo algoritmov, ktoré dokážu prehľadať danú informáciu v krátkom čase a poskytnúť ju používateľovi, aby mohol pokračovať v ďalších úlohách.
=> Úplný zoznam výukových programov C ++ nájdete tu.
Čo sa dozviete:
Techniky vyhľadávania
Máme dve hlavné techniky vyhľadávania, ktoré sa väčšinou používajú na vyhľadávanie informácií.
Tie obsahujú:
- Lineárne vyhľadávanie
- Binárne vyhľadávanie
V tomto výučbe podrobne preskúmame obe tieto techniky vyhľadávania.
Lineárne vyhľadávanie
Toto je najzákladnejšia technika vyhľadávania a je tiež ľahšie implementovateľná. Pri lineárnom vyhľadávaní sa kľúč, ktorý sa má vyhľadať, porovnáva lineárne s každým prvkom zhromažďovania údajov. Táto technika funguje efektívne na lineárnych dátových štruktúrach.
Uvažujme o nasledujúcom poli.
Hore je pole siedmich prvkov. Ak chceme hľadať kľúč = 23, tak začneme od nulythhodnota kľúča sa porovná s každým prvkom. Keď sa kľúčový prvok zhoduje s prvkom v poli, príslušné konkrétne miesto sa vráti. V takom prípade sa vráti hodnota 4, pretože pár kľúč - hodnota sa zhoduje s hodnotou v danom umiestnení.
Nižšie sme implementovali lineárne vyhľadávanie pomocou jazyka C ++ a Java.
Implementácia C ++
#include #include using namespace std; int main() { int myarray[10] = {21,43,23,54,75,13,5,8,25,10}; int key,loc; cout<<'The input array is'<key; for (int i = 0; i<10; i++) { if(myarray[i] == key) { loc = i+1; break; } else loc = 0; } if(loc != 0) { cout<<'Key found at position '< Výkon:
otázky týkajúce sa rozhovoru na základe scl
Vstupné pole je
21 43 23 54 75 13 5 8 25 10
Zadajte kľúč, ktorý chcete vyhľadať: 3
V poli sa nepodarilo nájsť daný kľúč
Vstupné pole je
21 43 23 54 75 13 5 8 25 10
Zadajte kľúč, ktorý chcete vyhľadať: 75
Kľúč nájdený na pozícii 5 v poli
Implementácia Java
import java.util.*; import java.lang.*; import java.io.*; public class Main { public static void main(String[] args) { int[] myarray = {21,43,23,54,75,13,5,8,25,10}; int key,location=0; Scanner sc = new Scanner(System.in); System.out.println('The input array is'); for(int i=0;i<10;i++){ System.out.print(myarray[i]+' '); } System.out.println('
'); System.out.println('Enter key'); key = sc.nextInt(); for(int i = 0; i<10; i++) { if(myarray[i]==key) { location = i+1; break; } else location = 0; } if(location != 0) { System.out.println('key found at location ' + location); } else System.out.println('Key not found'); } }
Výkon:
Vstupné pole je
21 43 23 54 75 13 5 8 25 10
Vstupný kľúč
2. 3
kľúč sa našiel na mieste 3
Lineárne vyhľadávanie je možné vykonať na akejkoľvek lineárnej dátovej štruktúre, ktorá má triedené alebo netriedené prvky. Trvá to však dlhšie, ak je prvkov príliš veľa a ak je kľúčový prvok na konci, pretože každý prvok sa porovnáva s hodnotou kľúča.
Binárne vyhľadávanie
Binárne vyhľadávanie je technika, ktorá využíva na vyhľadanie kľúča techniku „rozdeľ a panuj“. Funguje na zoradenom lineárnom zozname prvkov. Triedený zoznam je základnou požiadavkou fungovania binárneho vyhľadávania.
Pri metóde binárneho vyhľadávania je zoznam opakovane rozdelený na polovicu a kľúčový prvok sa prehľadáva v oboch poloviciach zoznamu, kým sa kľúč nenájde.
Napríklad,Zoberme si nasledujúce zoradené pole 10 prvkov.
Povedzme, že kľúč = 21 sa má hľadať v poli.
Vypočítajme stredné umiestnenie poľa.
Stred = 0 + 9/2 = 4
Napríklad,Zoberme si nasledujúce zoradené pole 10 prvkov.
Kľúč = 21
Najskôr porovnáme kľúčovú hodnotu s prvkom [mid]. Zistili sme, že hodnota prvku v strede = 21.
grafová dátová štruktúra c ++
Nájdeme teda tento kľúč = [stred]. Preto sa kľúč nachádza.
kľúč = 25
Najskôr porovnáme kľúčovú hodnotu so strednou. Takže (21<25), we will directly search for the key in the upper half of the array.
Teraz opäť nájdeme stred pre hornú polovicu poľa.
Stred = 4 + 9/2 = 6
Hodnota v umiestnení [v strede] = 25
Teraz porovnáme kľúčový prvok so stredným prvkom. Takže (25 == 25), teda sme našli kľúč na mieste [v strede].
Pole opakovane rozdelíme a porovnaním kľúčového prvku so stredom sa rozhodneme, v ktorej polovici kľúč vyhľadáme.
Ďalej uvádzame implementáciu C ++ a Java pre binárne vyhľadávanie.
Implementácia C ++
#include #include using namespace std; int binarySearch(int myarray[], int beg, int end, int key) { int mid; if(end >= beg) { mid = (beg + end)/2; if(myarray[mid] == key) { return mid+1; } else if(myarray[mid] key; location = binarySearch(myarray, 0, 9, key); if(location != -1) { cout<<'Key found at location '< Výkon:
Vstupné pole je
5 8 10 13 21 23 25 43 54 75
Zadajte kľúč, ktorý chcete vyhľadať: 21
Kľúč sa našiel na mieste 5
čo je chyba v testovaní softvéru s príkladom
Implementácia Java
import java.util.*; import java.lang.*; import java.io.*; class Main { public static void main(String[] args) { int[] myarray = {5,8,10,13,21,23,25,43,54,75}; int key, location = -1; System.out.println('The input array is'); for(int i=0;i= beg) { mid = (beg + end)/2; if(myarray[mid] == key) { return mid+1; } else if(myarray[mid] Výkon:
Vstupné pole je
5 8 10 13 21 23 25 43 54 75
Zadajte kľúč, ktorý chcete vyhľadať
dvadsaťjeden
umiestnenie kľúča je 5
Binárne vyhľadávanie je efektívnejšie z hľadiska času a správnosti. Technika lineárneho vyhľadávania sa používa zriedka, pretože je ťažkopádnejšia a pomalšia. Binárne vyhľadávanie je v porovnaní s lineárnym vyhľadávaním oveľa rýchlejšie.
Záver
Techniky vyhľadávania nám pomáhajú vyhľadávať informácie uložené v počítači, aby používateľ mohol pokračovať v ďalších úlohách spracovania informácií. Technika lineárneho vyhľadávania je jednoduchá a ľahšia, ale nepoužíva sa príliš často.
Technika binárneho vyhľadávania je oveľa rýchlejšia a efektívnejšia, a preto sa často používa.
V našom pripravovanom výučbe podrobne preskúmame rôzne techniky triedenia.
=> Vyskúšajte tu dokonalého školiaceho sprievodcu jazykom C ++.
Odporúčané čítanie
- Úvod do programovacieho jazyka Java - videonávod
- Úvod do aplikácie Appium Studio: Hlavné výhody a vlastnosti
- Algoritmy v STL
- Najlepšia výučbová séria C # ZDARMA: Sprievodca C # pre začiatočníkov
- JMeter Video 1: Úvod, stiahnutie a inštalácia JMeter
- Proces predstavenia a inštalácie Pythonu
- Čo je Unix: Stručný úvod do systému Unix
- Úvod do aplikácie Micro Focus LoadRunner - Testovanie zaťaženia s príručkou LoadRunner č. 1