Java >> Java tutorial >  >> Java

Lineær søgning i Java

Java

Lineær søgning eller sekventiel søgning i Java | Lineær søgning eller sekventiel søgning er en metode til at finde et element inden for en given liste eller matrix. Lineær søgning eller sekventiel søgning er normalt meget enkel at implementere og er praktisk, når listen kun har nogle få elementer, eller når du udfører en enkelt søgning i en uordnet liste.

Eksempel:-
Array ={50, 90, 30, 70, 60};

Input til søgning =30
Output:- 30 fundet i indeks 2.

Input til søgning =10
Output:- 10 blev ikke fundet.

Hvordan fungerer lineær søgning?

I Lineær søgning, finder indekset eller placeringen af ​​søgningen i den givne matrix. Den begynder søgningen ved at sammenligne søgenøglen og det første element i arrayet/listen. Hvis det første element ikke er lig med søgenøglen, vil det sammenlignes med det næste element, og så videre, indtil matchen er fundet eller slutningen af ​​arrayet. Hvis matchen findes, returnerer den sit indeks, ellers vil den nå slutningen af ​​arrayet eller listen, hvilket betyder, at søgenøglen ikke er tilgængelig.

Lad os forstå det gennem et eksempel:- Givet matrix ={50, 90, 30, 70, 60};

Antag at søgetasten =30; Gå derefter gennem arrayet og sammenlign med hvert element. Det første element i arrayet er 50, men 50 er ikke lig med 30, flyt derfor til det næste element. Det næste element er 90, men det er heller ikke lig med 30, flyt derfor til det næste element. Det næste element i arrayet er 30, hvilket er lig med søgenøglen 30, og returnerer derfor indekset for det aktuelle element i arrayet.

Det var den situation, hvor søgenøglen findes i arrayet, lad os nu antage, når søgenøglen ikke er tilgængelig. Antag søgetasten =10. Gå gennem arrayet og sammenlign med hvert element. Det vil ikke matche med 50, 90, 30, 70, 60 og nåede endelig slutningen af ​​arrayet. Returner derfor -1, hvilket betyder, at søgenøglen ikke er tilgængelig.

Lineær søgealgoritme i Java

Proceduren til at finde et element i en given matrix eller liste gennem lineær søgning,

a) Tag array, størrelsen på arrayet og søgetasten. Antag, at de er:- array, n og key
b) Gå gennem arrayet.
c) Sammenlign nøglen med hvert element.
d) Hvis matchen er fundet, så returner positionen .
e) Ellers gentag processen indtil slutningen af ​​arrayet.
f) Efter at have krydset arrayet Hvis matchen ikke findes, så returner -1.

Algoritmen for lineær eller sekventiel søgning kan angives som ,

linear search(array, n, key) {
   i = 0;
   while(i < n) {
      if(key == array[i])
        then return i;
      else
        i= i + 1;
   }
   return -1;  
}

Tidskompleksiteten af ​​ovenstående algoritme:- O(n)

  • Best-case ydeevne:- O(1) . Når søgenøglen er til stede ved det første indeks/position af arrayet, kræves der kun én sammenligning.
  • Worst case-ydeevne:- O(n) . Når søgenøglen er til stede ved det sidste indeks i arrayet, kræver det N-sammenligning, hvor N er størrelsen af ​​arrayet.

Lineært søgeprogram i Java

Lad os nu udvikle et Java-program til at demonstrere den lineære søgealgoritme. Vi vil udvikle en metode, der vil søge efter nøglen i det givne array ved hjælp af en lineær søgealgoritme.

import java.util.Scanner;

public class Search {

   public static void main(String[] args) {
      // Scanner class object to read input
      Scanner scan = new Scanner(System.in);
      
      // array
      int arr[] = { 50, 90, 30, 70, 60 };

      // read search key
      int key = 0;
      System.out.print("Enter search key: ");
      key = scan.nextInt();

      // find size of array
      int size = arr.length;

      // linear search
      int index = linearSearch(arr, size, key);

      // display result
      if (index == -1)
         System.out.println(key + " not Found.");
      else
         System.out.println(key + " Found at Index = " + index);
      
      // close Scanner class object
      scan.close();

   }

   public static int linearSearch(int[] arr, int size, int key) {
      // traverse through the array
      for (int i = 0; i < size; i++) {
         if (key == arr[i])
            return i;
      }
      return -1;
   }

}

Output:-

Indtast søgenøgle:30
30 fundet ved indeks =2

Indtast søgenøgle:99
99 ikke fundet.

Brug af egenskaben Length til at søge i matrixelementet

I Java har hvert array en indbygget egenskab til at gemme størrelsen af ​​arrayet, og vi kan få det gennem array.length, mens vi udvikler metoder i Java-programmeringssproget, behøver vi ikke at videregive størrelsen af ​​arrayet. Lad os udvikle det samme program uden at passere størrelsen af ​​arrayet.

import java.util.Scanner;

public class Search {

   public static void main(String[] args) {
      // Scanner class object to read input
      Scanner scan = new Scanner(System.in);
      
      // array
      int arr[] = { 50, 90, 30, 70, 60 };

      // read search key
      int key = 0;
      System.out.print("Enter search key: ");
      key = scan.nextInt();

      // linear search
      int index = linearSearch(arr, key);

      // display result
      if (index == -1)
         System.out.println(key + " not Found.");
      else
         System.out.println(key + " Found at Index = " + index);
      
      // close Scanner class object
      scan.close();

   }

   public static int linearSearch(int[] arr, int key) {
      // traverse through the array
      for (int i = 0; i < arr.length; i++) {
         if (key == arr[i])
            return i;
      }
      return -1;
   }
}

Lineær søgning efter String Array i Java

Lad os endnu et eksempel bruge String-arrayet i Java. Programbeskrivelse:- Skriv et Java-program for at finde et element fra et string-array ved hjælp af lineær søgning eller sekventiel søgning. 

import java.util.Scanner;

public class Search {

   public static void main(String[] args) {
      // Scanner class object to read input
      Scanner scan = new Scanner(System.in);
      
      // array
      String str[] = {"Java", "Python", "C++", "HTML", "CSS"};

      // read search key
      String key = null;
      System.out.print("Enter search key: ");
      key = scan.next();

      // linear search
      int index = linearSearch(str, key);

      // display result
      if (index == -1)
         System.out.println(key + " not Found.");
      else
         System.out.println(key + " Found at Index = " + index);
      
      // close Scanner class object
      scan.close();

   }

   public static int linearSearch(String[] arr, String key) {
      // traverse through the array
      for (int i = 0; i < arr.length; i++) {
         if (key.equals(arr[i]))
            return i;
      }
      return -1;
   }
}

Output:-

Indtast søgenøgle:Java
Java fundet ved indeks =0

Indtast søgenøgle:HTML
HTML fundet ved indeks =3

Indtast søgenøgle:Ruby
Ruby ikke fundet.

Indtast søgenøgle:Forår
Forår ikke fundet.

Lineær søgning ved hjælp af rekursion i Java

En metode, der indeholder et kald til sig selv, kaldes metoden. En teknik til at definere den rekursive metode kaldes rekursion. Den rekursive metode giver os mulighed for at opdele det komplekse problem i identiske enkelte simple tilfælde, der nemt kan håndteres. Dette er også en velkendt computerprogrammeringsteknik:del og hersk.

import java.util.Scanner;

public class Search {

   public static void main(String[] args) {
      // Scanner class object to read input
      Scanner scan = new Scanner(System.in);

      // array
      int arr[] = { 50, 90, 30, 70, 60 };

      // read search key
      int key = 0;
      System.out.print("Enter search key: ");
      key = scan.nextInt();

      // linear search
      int index = linear(arr, 0, key);

      // display result
      if (index == -1)
         System.out.println(key + " not Found.");
      else
         System.out.println(key + " Found at Index = " + index);

      // close Scanner class object
      scan.close();
   }

   public static int linear(int arr[], int index, int key) {
      if (index >= arr.length)
         return -1;
      else if (arr[index] == key)
         return index;
      else
         return linear(arr, index + 1, key);
   }

}

Forbedret version

Vi får worst-case ydeevne O(n), fordi vi kun sammenligner array-elementer fra den ene side. I stedet for den ene side, hvis vi sammenligner array-elementerne fra begge ender, dvs. forfra og sidst, vil det reducere antallet af iterationer . Lad os forstå det gennem et eksempel,

Matrix ={10, 20, 30, 40, 50};
Søgetast =40;

  • I den første iteration er 40 ikke lig med 10 (fra venstre side), og 40 er ikke lig med 50 (fra højre side).
  • I den anden iteration er 40 ikke lig med 20 (fra venstre side), men 40 er lig med 40.
  • Derfor findes søgenøglen i indeks 3.

Den normale lineære søgning kan finde den i 4 iterationer, men en forbedret lineær søgning kan finde den i kun 2 iterationer.

Java program til ovenstående forbedrede lineære søgning ,

import java.util.Scanner;

public class Search2 {

   public static void main(String[] args) {
      // Scanner class object to read input
      Scanner scan = new Scanner(System.in);

      // array
      int arr[] = { 50, 90, 30, 70, 60 };

      // read search key
      int key = 0;
      System.out.print("Enter search key: ");
      key = scan.nextInt();

      // linear search
      int index = linearSearch(arr, key);

      // display result
      if (index == -1)
         System.out.println(key + " not Found.");
      else
         System.out.println(key + " Found at Index = " + index);

      // close Scanner class object
      scan.close();
   }

   // Method for improved linear search
   // if match found then return index of search key else return -1
   public static int linearSearch(int arr[], int key) {
      int n = arr.length;
      for(int i=0, j=n-1; i<=n/2; i++, j--)  {
        if(key == arr[i])
         return i;
        if(key == arr[j])
         return j;
      }
      return -1;
   }

}

Output:-

Indtast søgenøgle:70
70 fundet ved indeks =3

Den bedste tidskompleksitet er den samme som tidligere:O(1)
Den værste tidskompleksitet:- O(n/2)

Se også,

  • Lineær søgealgoritme i DSA
  • C-program til lineær søgning
  • C++-program til lineær søgning
  • Python-program til lineær søgning

Java tag