Programa Java para búsqueda lineal

Problema: Dada una array arr[] de n elementos, escriba una función para buscar un elemento dado x en arr[]. 

ALGORITMO:
Paso 1: Iniciar 
Paso 2: Declarar una array y buscar elemento como clave.
Paso 3: recorrer la array hasta encontrar el número.
Paso 4: si se encuentra el elemento clave, devolver la posición de índice del elemento de array
Paso 5: si no se encuentra el elemento clave, devolver -1
Paso 6: Detener.
 

Pseudocódigo :
PROCEDIMIENTO LINEAR_SEARCH (LISTA, VALOR)
  PARA CADA ARTÍCULO EN LA LISTA
     SI EL MISMO ARTÍCULO == VALOR
          DEVOLVER LA UBICACIÓN DEL ARTÍCULO
     FIN SI
  FIN PARA
FIN DEL PROCEDIMIENTO
 

// Java code for linearly search x in arr[]. If x
// is present then return its location, otherwise
// return -1
class LinearSearch {
    // This function returns index of element x in arr[]
    static int search(int arr[], int n, int x)
    {
        for (int i = 0; i < n; i++) {
            // Return the index of the element if the element
            // is found
            if (arr[i] == x)
                return i;
        }
 
        // return -1 if the element is not found
        return -1;
    }
 
    public static void main(String[] args)
    {
        int[] arr = { 3, 4, 1, 7, 5 };
        int n = arr.length;
         
        int x = 4;
 
        int index = search(arr, n, x);
        if (index == -1)
            System.out.println("Element is not present in the array");
        else
            System.out.println("Element found at position " + index);
    }
}

Element found at position 1

Complejidad del tiempo:

COMPLEJIDAD DEL MEJOR CASO 
En la búsqueda lineal, el mejor caso ocurre cuando el elemento de búsqueda está presente en la primera ubicación de la array. Entonces, la complejidad temporal de la búsqueda lineal en el mejor de los casos es o(1). 

En el mejor de los casos, la complejidad temporal de la búsqueda lineal es o(1).

COMPLEJIDAD PROMEDIO DEL CASO 
En la búsqueda lineal, el caso promedio ocurre cuando el elemento de búsqueda está presente en la ubicación aleatoria de la array, por lo que la complejidad promedio del tiempo del caso de la búsqueda lineal es o (1).
La complejidad de tiempo de caso promedio de la búsqueda lineal es o(n).

COMPLEJIDAD EN EL PEOR CASO
En la búsqueda lineal, el peor caso ocurre cuando el elemento de búsqueda está presente en la última ubicación de la array. Por lo tanto, la complejidad temporal en el peor caso de la búsqueda lineal es o(1). El elemento no está presente en la array dada, entonces necesitamos recorrer toda la array para buscar el elemento. Entonces, la complejidad temporal de la búsqueda lineal en el peor de los casos es o(n).
La complejidad temporal en el peor de los casos de la búsqueda lineal es o(n)

COMPLEJIDAD ESPACIAL: 
La complejidad ESPACIAL de la búsqueda lineal es o(1)

Aplicaciones de búsqueda lineal

usamos la búsqueda lineal en las siguientes cosas:
• para el elemento de búsqueda en la array más pequeña.
• Para búsqueda rápida 
La complejidad temporal del algoritmo anterior es O(n). Consulte el artículo completo sobre Búsqueda lineal para obtener más detalles.