logo

TechCodeview

Sökalgoritmer

Sökande algoritmer är viktiga verktyg inom datavetenskap som används för att lokalisera specifika objekt i en datasamling. Dessa algoritmer är designade för att effektivt navigera genom datastrukturer för att hitta den önskade informationen, vilket gör dem grundläggande i olika applikationer som t.ex. databaser, webbsökmotorer , och mer.

Sökalgoritm

länkad lista java

Innehållsförteckning



Vad är sökning?

Att söka är den grundläggande processen för att lokalisera ett specifikt element eller objekt i en datasamling . Denna insamling av data kan ta olika former, såsom arrayer, listor, träd eller andra strukturerade representationer. Det primära syftet med sökningen är att avgöra om det önskade elementet finns i data, och i så fall att identifiera dess exakta plats eller hämta den. Det spelar en viktig roll i olika beräkningsuppgifter och verkliga tillämpningar, inklusive informationssökning, dataanalys, beslutsprocesser och mer.

Söker efter terminologier:

Målelement:

Vid sökning finns det alltid ett specifikt målelement eller objekt som du vill hitta inom datainsamlingen. Detta mål kan vara ett värde, en post, en nyckel eller någon annan dataenhet av intresse.

Sökutrymme:

Sökutrymmet avser hela samlingen av data inom vilken du söker efter målelementet. Beroende på vilken datastruktur som används kan sökutrymmet variera i storlek och organisation.

Komplexitet:

Sökning kan ha olika komplexitetsnivåer beroende på datastrukturen och vilken algoritm som används. Komplexiteten mäts ofta i termer av tids- och platsbehov.

till strängmetoden java

Deterministisk vs. icke-deterministisk:

Vissa sökalgoritmer, som binär sökning , är deterministiska, vilket innebär att de följer ett tydligt, systematiskt tillvägagångssätt. Andra, såsom linjär sökning, är icke-deterministiska, eftersom de i värsta fall kan behöva undersöka hela sökutrymmet.

Vikten av att söka i DSA:

  • Effektivitet: Effektiva sökalgoritmer förbättrar programmets prestanda.
  • Datahämtning: Hitta och hämta snabbt specifik data från stora datamängder.
  • Databassystem: Möjliggör snabb sökning av databaser.
  • Problemlösning: Används i ett brett utbud av problemlösningsuppgifter.

Applikationer för sökning:

Sökalgoritmer har många tillämpningar inom olika områden. Här är några vanliga applikationer:

  • Informationsinhämtning: Sökmotorer som Google, Bing och Yahoo använder sofistikerade sökalgoritmer för att hämta relevant information från stora mängder data på webben.
  • Databassystem: Sökning är grundläggande i databassystem för att hämta specifika dataposter baserat på användarfrågor, vilket förbättrar effektiviteten vid datahämtning.
  • E-handel: Sökning är avgörande i e-handelsplattformar för att användare snabbt ska hitta produkter baserat på deras preferenser, specifikationer eller sökord.
  • Nätverk: I nätverk används sökalgoritmer för att dirigera paket effektivt genom nätverk, hitta optimala vägar och hantera nätverksresurser.
  • Artificiell intelligens: Sökalgoritmer spelar en viktig roll i AI-tillämpningar, såsom problemlösning, spel (t.ex. schack) och beslutsprocesser
  • Mönsterigenkänning: Sökalgoritmer används i mönstermatchningsuppgifter, som bildigenkänning, taligenkänning och handskriftsigenkänning.

Grunderna i sökalgoritmer:

  • Introduktion till sökning – Handledning för datastruktur och algoritm
  • Vikten av att söka i Data Structure
  • Vad är syftet med sökalgoritmen?

Sökalgoritmer:

  • Linjär sökning
  • Sentinel linjär sökning
  • Binär sökning
  • Meta binär sökning | Ensidig binär sökning
  • Ternär sökning
  • Hoppa Sök
  • Interpolationssökning
  • Exponentiell sökning
  • Fibonacci-sökning
  • Den allestädes närvarande binära sökningen

Jämförelser mellan olika sökalgoritmer:

  • Linjär sökning vs binär sökning
  • Interpolationssökning vs binär sökning
  • Varför föredras binär sökning framför ternär sökning?
  • Är Sentinel Linear Search bättre än vanlig linjär sökning?

Biblioteksimplementeringar av sökalgoritmer:

  • Binära sökfunktioner i C++ STL (binary_search, lower_bound och upper_bound)
  • Arrays.binarySearch() i Java med exempel | Set 1
  • Arrays.binarySearch() i Java med exempel | Set 2 (Sök i subarray)
  • Collections.binarySearch() i Java med exempel

Enkla problem vid sökning:

  • Hitta de tre största elementen i en array
  • Hitta det saknade numret
  • Hitta det första upprepande elementet i en array av heltal
  • Hitta det saknade och upprepade numret
  • Sök, infoga och ta bort i en sorterad array
  • Räkna 1:or i en sorterad binär array
  • Två element vars summa är närmast noll
  • Hitta ett par med den givna skillnaden
  • k största (eller minsta) element i en array
  • K:te minsta elementet i en rad- och kolumnvis sorterad 2D-matris
  • Hitta vanliga element i tre sorterade arrayer
  • Tak i en sorterad array
  • Golv i en sorterad array
  • Hitta det maximala elementet i en array som först ökar och sedan minskar
  • Med tanke på en matris av storleken n och ett tal k, hitta alla element som visas fler än n/k gånger

Medelstora problem vid sökning:

  • Hitta alla trillingar med nollsumma
  • Hitta elementet före vilket alla element är mindre än det, och efter vilket alla är större
  • Hitta den största parsumman i en osorterad matris
  • K'th minsta/största element i osorterad array
  • Sök efter ett element i en sorterad och roterad array
  • Hitta minimielementet i en sorterad och roterad array
  • Hitta ett toppelement
  • Maximalt och minimum av en array med minsta antal jämförelser
  • Hitta en fast punkt i en given array
  • Hitta de k vanligaste orden från en fil
  • Hitta k element som ligger närmast ett givet värde
  • Givet en sorterad matris och ett nummer x, hitta det par i matris vars summa är närmast x
  • Hitta det närmaste paret från två sorterade arrayer
  • Hitta tre närmaste element från givna tre sorterade arrayer
  • Binär sökning efter rationella tal utan att använda aritmetik med flyttal

Svåra problem vid sökning:

  • Median för två sorterade arrayer
  • Median av två sorterade arrayer av olika storlekar
  • Sök i en nästan sorterad array
  • Hitta positionen för ett element i en sorterad matris med oändliga tal
  • Givet en sorterad och roterad matris, hitta om det finns ett par med en given summa
  • K’th minsta/största element i osorterad array | I värsta fall linjär tid
  • K'th största element i en bäck
  • Bästa första sökningen (informerad sökning)

Snabblänkar:

  • 'Övningsproblem' vid sökning
  • 'Frågesporter' om sökning

Rekommenderad:

  • Lär dig datastruktur och algoritmer | Handledning för DSA