• Acasă
  • Despre noi
  • Autori
  • Mărturii
  • Arhivă
  • Trimite Articol
  • Contact

WORLDIT

Lumea în 1 și 0.

  • Știri
    • Tehnologie
    • Tehnologie mobilă
    • Securitate
    • Developers
    • Știință
    • Benzi desenate
    • Jocuri
    • Intern
  • Tehnic
    • Browser
    • C#
    • C/C++
    • Challenge
    • HTML/CSS
    • Javascript, Ajax, jQuery
    • Open Source
    • PHP
    • Python
    • Securitate IT
    • Socializare
    • WordPress
    • Altele
  • Recenzii
  • Interviuri
  • Evenimente

Cautarea unui element intr-un vector

1
  • Publicat de Coss
  • în C/C++
  • — 27 sept., 2009 at 9:08 pm

C plus plusIn urmatorul articol vom prezenta cele 2 tipuri de cautare ale unui element intr-un vecor.

1) Cautarea Secventiala

Acest algoritm cauta elementul succesiv in componentele vectorului. Un caz practic ar fi exemplul cautarii unui nume in cartea de telefon. Deschidem cartea la intamplare,dorim sa cautam numele „Popa Andrei „. Verificam daca numele se afla in prima partea a cartii sau in a doua parte. Continuam cautarea in portiunea respectiva, actiunea se repeta pana la gasirea numelui.

La fel este si in cazul numerelor dintr-un vector.

#include <iostream>

int main()
{
    int n,v[100],i,gasit=0,x;
    cout<<"Dati n : ";cin>>n;
    cout<<"Dati nr pe care trebuie sa-l cautam: ";cin>>x;
    for (i=0;i<n;i++)
    {
         cout<<"v["<<i+1<<"]=";cin>>v[i];
    }
    i=1;
    while ( (i<=n) && (!gasit) )
   {
       if (v[i]==x) gasit=1;
       i++;
   }
   if (gasit) cout<<x<<" se afla in vector";
   else cout<<x<<" nu se afla in vector";

   return 0;
}

Cautarea secventiala se poate face intr-un vector cu elementele neordonate.Astfel complexitatea algoritmului este liniara : O(n).

caut_secv
2) Cautarea Binara

Cautarea binara se bazeaza pe tehnica de programare Divide et Impera. Elementul cautat este „verificat” cu mijlocul vectorului. Daca elementul este egal cu mijlocul,cautarea se termina. Insa daca nu sunt egale, se compara valoarea mijlocului cu cea a elementului de cautat. Daca elementul este mai mare se continua cautarea de la mijlocul listei pana la sfarsit, iar daca este mai mic se continua cautarea de la inceput pana la mijloc.

#include <iostream.h>

int main()
{
    int mij,n=7,i,x=10,v[7]={4,5,8,10,20,45,76},st,dr,g=0;
    st=0;
    dr=n-1;
    mij=(st+dr)/2;
    while  ( (st<dr) && (!g) )
    {
         if (v[mij]==x) {g=1;break;}
         else if (v[mij]<x) st=mij+1;
         else if (v[mij]>x) dr=mij-1;
    }
    if (g) cout<<x<<" se afla in vector pe pozitia "<<mij;
    else cout<<x<<" nu se afla in vector";

    return 0;
}

De aceasta data am dat elementele vectorului si numarul cautat, nu le-am mai citit. Observam ca am folosit o tehnica numita divide si cucereste. Dupa cum bine stim de la clasicul QuickSort orice algoritm divide si cucereste are timp logaritmic. 🙂

caut_bin

Etichete: cautare binaracautare secventialaelementprogramvector

— Albulescu Cosmina a scris 223 articole

Nu există o descriere a autorului.

  • Articolul anterior Extensii pentru Google Chrome marca WorldIT
  • Articolul următor Sistemul de organizare al furnicilor inspira noua generatia de antivirusi

1 Comentariu

  1. Ana Evelyn spune:
    mai 5, 2016 la 5:55 am

    La cautarea binara mjlocul ar trebui modificat in while, adica dupa
    while(conditie)
    { mij=(st+dr)/2;
    if …
    }


  • Facebook

    WorldIT.info
  • Ultimele Atacuri Cibernetice din Romania – RO Hacked

    [wp_rss_retriever url="https://rohacked.bit-sentinel.com/feed/" excerpt="none" items="5" read_more="false" new_window="true" thumbnail="false" cache="0"] RO Hacked este registrul atacurilor cibernetice din România.
  • Caută

  • Articole Recomandate

    • Recent Posts
    • Tags
    • Număr record de participanți la DefCamp 2015, cel mai important eveniment dedicat securității cibernetice din Europe Centrala si de Estdecembrie 2, 2015
    • La DefCamp 2015 vei afla prin ce tehnici pot fi evitate măsurile de securitate ale sistemelor informatice criticeoctombrie 16, 2015
    • Ultima sansa sa rezervi bilete de tip Early Bird la DefCamp 2015septembrie 1, 2015
    • 15 sfaturi despre cum poti deveni un programator bun venite de la specialisti romaniaugust 4, 2015
    • algoritmica Android antivirus Apple Avadanei Andrei benzi desenate BitDefender blog browser C++ Chrome concurs eveniment Facebook Firefox Google google chrome hacking html5 infografic informatica internet Internet Explorer IT javascript linux Microsoft Mozilla Firefox online PHP programare retea sociala review Romania securitate Tehnologie Twitter web Windows Windows 7 Wordpress WorldIT worldit.info Yahoo! YouTube
  • mai 2023
    L Ma Mi J V S D
    1234567
    891011121314
    15161718192021
    22232425262728
    293031  
    « dec.    
  • Link-uri Sponsorizate

    • laptop second hand

    • Calculatoare Second Hand

    • cod voucher pc garage

  • Home
  • Tehnic
  • C/C++
  • Cautarea unui element intr-un vector
  • Important

    • Bit Sentinel
    • Centrul de Cercetare în Securitate Informatică din România
    • DefCamp
  • Prieteni

    • BetiT.ro
    • bijuterii handmade
    • Computerica | Resurse gratuite PC
    • Descopera.org
    • Gadgeturi si IT – Giz.ro
  • Prieteni

    • PC – Config
    • RO Hacked
    • Stiri IT

Copyright © 2009-2014 WORLDIT. Toate drepturile Rezervate.
Termeni și condiții | Contact | Licența Creative Commons