Tässä opetusohjelmassa opit lineaarisesta hausta. Löydät myös toimivia esimerkkejä lineaarisesta hausta C, C ++, Java ja Python.
Lineaarinen haku on yksinkertaisin hakualgoritmi, joka etsii elementtiä luettelosta peräkkäisessä järjestyksessä. Aloitamme toisesta päästä ja tarkistamme jokaisen elementin, kunnes haluttua elementtiä ei löydy.
Kuinka lineaarinen haku toimii?
Seuraavia vaiheita noudatetaan etsiäksesi elementtiä k = 1alla olevasta luettelosta.
Taulukko etsittäväksi
- Aloita ensimmäisestä elementistä, vertaa k kullekin elementille x.
Vertaa jokaiseen elementtiin - Jos
x == k, palauta hakemisto.
Elementti löydetty - Muuten palautusta ei löydy.
Lineaarinen hakualgoritmi
Lineaarinen haku (taulukko, avain) jokaiselle matriisin kohteelle, jos item == value palauttaa hakemistonsa
Python-, Java- ja C / C ++ -esimerkkejä
Python Java C C ++ # Linear Search in Python def linearSearch(array, n, x): # Going through array sequencially for i in range(0, n): if (array(i) == x): return i return -1 array = (2, 4, 0, 1, 9) x = 1 n = len(array) result = linearSearch(array, n, x) if(result == -1): print("Element not found") else: print("Element found at index: ", result)
// Linear Search in Java class LinearSearch ( public static int linearSearch(int array(), int x) ( int n = array.length; // Going through array sequencially for (int i = 0; i < n; i++) ( if (array(i) == x) return i; ) return -1; ) public static void main(String args()) ( int array() = ( 2, 4, 0, 1, 9 ); int x = 1; int result = linearSearch(array, x); if (result == -1) System.out.print("Element not found"); else System.out.print("Element found at index: " + result); ) )
// Linear Search in C #include int search(int array(), int n, int x) ( // Going through array sequencially for (int i = 0; i < n; i++) if (array(i) == x) return i; return -1; ) int main() ( int array() = (2, 4, 0, 1, 9); int x = 1; int n = sizeof(array) / sizeof(array(0)); int result = search(array, n, x); (result == -1) ? printf("Element not found") : printf("Element found at index: %d", result); )
// Linear Search in C++ #include using namespace std; int search(int array(), int n, int x) ( // Going through array sequencially for (int i = 0; i < n; i++) if (array(i) == x) return i; return -1; ) int main() ( int array() = (2, 4, 0, 1, 9); int x = 1; int n = sizeof(array) / sizeof(array(0)); int result = search(array, n, x); (result == -1) ? cout << "Element not found" : cout << "Element found at index: " << result; )
Lineaarisen haun monimutkaisuus
Ajan monimutkaisuus: O (n)
Avaruuden monimutkaisuus: O(1)
Lineaariset hakusovellukset
- Hakutoimintoihin pienemmissä ryhmissä (<100 kohdetta).
