Menu

Úvod do vyhledávání algoritmů v C ++

introduction searching algorithms c

Vyzkoušejte Náš Nástroj Pro Odstranění Problémů

Přehled vyhledávání algoritmů v C ++.

Stále hledáme něco nebo jiného v našem každodenním životě. Stejně jako v každodenním životě musíme jako softwarový profesionál hledat informace na svém počítači. Vyhledávání informací by mělo probíhat rychle, protože si nemůžeme dovolit ztrácet většinu času hledáním informací.

Proto potřebujeme několik efektivních vyhledávacích technik nebo algoritmů, které dokážou prohledat danou informaci v krátké době a poskytnout ji uživateli, aby mohl pokračovat v dalších úkolech.

=> Úplný seznam výukových programů C ++ naleznete zde.

VYHLEDÁVÁNÍ ALGORITMŮ V C ++

Co se naučíte:

Techniky vyhledávání

Máme dvě hlavní techniky vyhledávání, které se většinou používají k hledání informací.

Tyto zahrnují:

  • Lineární vyhledávání
  • Binární vyhledávání

V tomto kurzu podrobně prozkoumáme obě tyto vyhledávací techniky.

Lineární vyhledávání

Toto je nejzákladnější vyhledávací technika a je také snazší implementovat. V lineárním vyhledávání je klíč, který má být prohledán, lineárně porovnán s každým prvkem sběru dat. Tato technika funguje efektivně na lineárních datových strukturách.

Zvažme následující pole.

Pole lineárního vyhledávání

Nahoře je pole sedmi prvků. Pokud chceme hledat klíč = 23, pak počínaje od 0thprvek, hodnota klíče bude porovnána s každým prvkem. Jakmile se klíčový prvek shoduje s prvkem v poli, vrátí se dané umístění. V tomto případě bude vrácena hodnota 4, protože se klíč – hodnota shoduje s hodnotou v daném místě.

Níže jsme implementovali lineární vyhledávání pomocí jazyka C ++ a Java.

Implementace 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ýstup:

java vývojář rozhovor otázky a odpovědi pro nováčky

Vstupní pole je
21 43 23 54 75 13 5 8 25 10
Zadejte hledaný klíč: 3
Nelze najít daný klíč v poli

Vstupní pole je
21 43 23 54 75 13 5 8 25 10
Zadejte hledaný klíč: 75
Klíč nalezen na pozici 5 v poli

Implementace 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ýstup:

Vstupní pole je

21 43 23 54 75 13 5 8 25 10

Zadejte klíč

2. 3

klíč nalezen na místě 3

Lineární vyhledávání lze provádět na jakékoli lineární datové struktuře obsahující tříděné nebo netříděné prvky. Trvá ale déle, pokud je prvků příliš mnoho a klíčový prvek je na konci, protože každý prvek je porovnáván s hodnotou klíče.

Binární vyhledávání

Binární vyhledávání je technika, která k hledání klíče používá techniku ​​„rozděl a panuj“. Funguje na seřazeném lineárním seznamu prvků. Seřazený seznam je základním požadavkem, aby binární vyhledávání fungovalo.

V metodě binárního vyhledávání je seznam opakovaně rozdělen na polovinu a klíčový prvek je prohledáván v obou polovinách seznamu, dokud není klíč nalezen.

Například,vezměme si následující seřazené pole 10 prvků.

Binární vyhledávání

Řekněme, že klíč = 21 má být prohledán v poli.

nejlepší vr headset pro Xbox One

Pojďme vypočítat střední umístění pole.

Polovina = 0 + 9/2 = 4

Například,vezměme si následující seřazené pole 10 prvků.

vypočítat střední umístění

Klíč = 21

Nejprve porovnáme hodnotu klíče s prvkem (mid). Zjistili jsme, že hodnota prvku v polovině = 21.

porovnejte hodnotu klíče s prvkem (mid)

Zjistili jsme tedy, že klíč = (uprostřed). Proto je klíč nalezen.

klíč = 25

klíč = (střední)

Nejprve porovnáme klíčovou hodnotu se střední hodnotou. Takže (21<25), we will directly search for the key in the upper half of the array.

porovnejte klíčovou hodnotu se střední

Nyní znovu najdeme střed pro horní polovinu pole.

Polovina = 4 + 9/2 = 6

Hodnota v umístění (mid) = 25

Hodnota v umístění (mid) = 25

Nyní porovnáme klíčový prvek se středním prvkem. Takže (25 == 25), tedy jsme našli klíč na místě (uprostřed).

Pole opakovaně rozdělíme a porovnáním klíčového prvku se středem se rozhodneme, ve které polovině klíč hledat.

Níže jsou uvedeny implementace C ++ a Java pro binární vyhledávání.

Implementace 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ýstup:

Vstupní pole je
5 8 10 13 21 23 25 43 54 75
Zadejte klíč, který chcete prohledat: 21
Klíč nalezen na místě 5

Binární vyhledávání c ++

Implementace 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ýstup:

Vstupní pole je

5 8 10 13 21 23 25 43 54 75

Zadejte klíč, který chcete prohledat

dvacet jedna

čím otevřít soubory SWF

umístění klíče je 5

Binární vyhledávání je efektivnější z hlediska času a správnosti. Technika lineárního vyhledávání se používá jen zřídka, protože je těžkopádnější a pomalejší. Binární vyhledávání je ve srovnání s lineárním vyhledáváním mnohem rychlejší.

Závěr

Techniky vyhledávání nám pomáhají hledat informace uložené v počítači, aby uživatel mohl pokračovat v dalších úkolech zpracování informací. Technika lineárního vyhledávání je jednoduchá a jednodušší, ale není příliš využívána.

Technika binárního vyhledávání je mnohem rychlejší a efektivnější, a proto se hojně používá.

V našem nadcházejícím výukovém programu podrobně prozkoumáme různé techniky řazení.

=> Podívejte se na průvodce Perfect C ++ Training Guide zde.

Doporučené čtení

^