Mejora de la técnica de búsqueda lineal

Una búsqueda lineal o búsqueda secuencial es un método para encontrar un elemento dentro de una lista. Comprueba secuencialmente cada elemento de la lista hasta que se encuentra una coincidencia o se ha buscado en toda la lista. Se observa que cuando se busca un elemento clave , existe la posibilidad de buscar el mismo elemento clave una y otra vez.

El objetivo es que si se vuelve a buscar el mismo elemento, la operación debe llevar menos tiempo. Por lo tanto, en tal caso, la búsqueda lineal se puede mejorar utilizando los dos métodos siguientes: 

1. Transposición
2. Mover al frente

Transposición :

En la transposición, si se encuentra el elemento clave, se cambia al elemento un índice antes para aumentar el número de búsquedas para una clave en particular, la operación de búsqueda también optimiza y sigue moviendo el elemento al comienzo de la array donde el la complejidad del tiempo de búsqueda sería de tiempo constante. 

Por ejemplo: si la array arr[] es {2, 5, 7, 1, 6, 4, 5, 8, 3, 7} y la clave a buscar es 4, a continuación se muestran los pasos: 

• Después de buscar la clave 4 , el elemento se encuentra en el índice 5 de la array dada después de 6 comparaciones. Ahora, después de la transposición, la array se convierte en {2, 5, 7, 1, 4, 6, 5, 8, 3, 7}, es decir, la clave con valor 4 viene en el índice 4.
• Nuevamente, después de buscar la clave 4 , el elemento se encuentra en el índice 4 de la array dada después de 6 comparaciones. Ahora, después de la transposición, la array se convierte en {2, 5, 7, 4, 1, 6, 5, 8, 3, 7}, es decir, la clave con valor 4 viene en el índice 3.
• El proceso anterior continuará hasta que cualquier clave llegue al frente de la array si el elemento a buscar no está en el primer índice.

A continuación se muestra la implementación del algoritmo anterior discutido:

// C++ program for transposition to
// improve the Linear Search Algorithm
#include <iostream>
using namespace std;
 
// Structure of the array
struct Array {
 
    int A[10];
    int size;
    int length;
};
 
// Function to print the array element
void Display(struct Array arr)
{
    int i;
 
    // Traverse the array arr[]
    for (i = 0; i < arr.length; i++) {
        cout <<" "<< arr.A[i];
    }
    cout <<"\n";
}
 
// Function that swaps two elements
// at different addresses
void swap(int* x, int* y)
{
    // Store the value store at
    // x in a variable temp
    int temp = *x;
 
    // Swapping of value
    *x = *y;
    *y = temp;
}
 
// Function that performs the Linear
// Search Transposition
int LinearSearchTransposition(
    struct Array* arr, int key)
{
    int i;
 
    // Traverse the array
    for (i = 0; i < arr->length; i++) {
 
        // If key is found, then swap
        // the element with it's
        // previous index
        if (key == arr->A[i]) {
 
            // If key is first element
            if (i == 0)
                return i;
 
            swap(&arr->A[i],
                 &arr->A[i - 1]);
 
            return i;
        }
    }
    return -1;
}
 
// Driver Code
int main()
{
    // Given array arr[]
    struct Array arr
        = { { 2, 23, 14, 5, 6, 9, 8, 12 },
            10,
            8 };
 
    cout <<"Elements before Linear"
           " Search Transposition: ";
 
    // Function Call for displaying
    // the array arr[]
    Display(arr);
 
    // Function Call for transposition
    LinearSearchTransposition(&arr, 14);
 
    cout <<"Elements after Linear"
           " Search Transposition: ";
 
    // Function Call for displaying
    // the array arr[]
    Display(arr);
    return 0;
}
 
// this code is contributed by shivanisinghss2110

// C program for transposition to
// improve the Linear Search Algorithm
#include <stdio.h>
 
// Structure of the array
struct Array {
 
    int A[10];
    int size;
    int length;
};
 
// Function to print the array element
void Display(struct Array arr)
{
    int i;
 
    // Traverse the array arr[]
    for (i = 0; i < arr.length; i++) {
        printf("%d ", arr.A[i]);
    }
    printf("\n");
}
 
// Function that swaps two elements
// at different addresses
void swap(int* x, int* y)
{
    // Store the value store at
    // x in a variable temp
    int temp = *x;
 
    // Swapping of value
    *x = *y;
    *y = temp;
}
 
// Function that performs the Linear
// Search Transposition
int LinearSearchTransposition(
    struct Array* arr, int key)
{
    int i;
 
    // Traverse the array
    for (i = 0; i < arr->length; i++) {
 
        // If key is found, then swap
        // the element with it's
        // previous index
        if (key == arr->A[i]) {
 
            // If key is first element
            if (i == 0)
                return i;
 
            swap(&arr->A[i],
                 &arr->A[i - 1]);
 
            return i;
        }
    }
    return -1;
}
 
// Driver Code
int main()
{
    // Given array arr[]
    struct Array arr
        = { { 2, 23, 14, 5, 6, 9, 8, 12 },
            10,
            8 };
 
    printf("Elements before Linear"
           " Search Transposition: ");
 
    // Function Call for displaying
    // the array arr[]
    Display(arr);
 
    // Function Call for transposition
    LinearSearchTransposition(&arr, 14);
 
    printf("Elements after Linear"
           " Search Transposition: ");
 
    // Function Call for displaying
    // the array arr[]
    Display(arr);
    return 0;
}

// Java program for transposition
// to improve the Linear Search
// Algorithm
class GFG{
 
// Structure of the
// array
static class Array
{
  int []A = new int[10];
  int size;
  int length;
  Array(int []A, int size,
        int length)
  {
    this.A = A;
    this.size = size;
    this.length = length;
  }
};
 
// Function to print the
// array element
static void Display(Array arr)
{
  int i;
 
  // Traverse the array arr[]
  for (i = 0; i < arr.length; i++)
  {
    System.out.printf("%d ",
                      arr.A[i]);
  }
  System.out.printf("\n");
}
 
// Function that performs the Linear
// Search Transposition
static int LinearSearchTransposition(Array arr,
                                     int key)
{
  int i;
 
  // Traverse the array
  for (i = 0; i < arr.length; i++)
  {
    // If key is found, then swap
    // the element with it's
    // previous index
    if (key == arr.A[i])
    {
      // If key is first element
      if (i == 0)
        return i;
      int temp = arr.A[i];
      arr.A[i] = arr.A[i - 1];
      arr.A[i - 1] = temp;
      return i;
    }
  }
  return -1;
}
 
// Driver Code
public static void main(String[] args)
{
  // Given array arr[]
  int tempArr[] = {2, 23, 14, 5,
                   6, 9, 8, 12};
  Array arr = new Array(tempArr,
                        10, 8);
 
  System.out.printf("Elements before Linear" +
                    " Search Transposition: ");
 
  // Function Call for displaying
  // the array arr[]
  Display(arr);
 
  // Function Call for transposition
  LinearSearchTransposition(arr, 14);
 
  System.out.printf("Elements after Linear" +
                    " Search Transposition: ");
 
  // Function Call for displaying
  // the array arr[]
  Display(arr);
}
}
 
// This code is contributed by Princi Singh

// C# program for transposition
// to improve the Linear Search
// Algorithm
using System;
 
class GFG{
 
// Structure of the
// array
public class Array
{
    public int []A = new int[10];
    public int size;
    public int length;
     
    public Array(int []A, int size,
                 int length)
    {
        this.A = A;
        this.size = size;
        this.length = length;
    }
};
 
// Function to print the
// array element
static void Display(Array arr)
{
    int i;
     
    // Traverse the array []arr
    for(i = 0; i < arr.length; i++)
    {
        Console.Write(arr.A[i] + " ");
    }
    Console.Write("\n");
}
 
// Function that performs the Linear
// Search Transposition
static int LinearSearchTransposition(Array arr,
                                     int key)
{
    int i;
     
    // Traverse the array
    for(i = 0; i < arr.length; i++)
    {
         
        // If key is found, then swap
        // the element with it's
        // previous index
        if (key == arr.A[i])
        {
             
            // If key is first element
            if (i == 0)
                return i;
                 
            int temp = arr.A[i];
            arr.A[i] = arr.A[i - 1];
            arr.A[i - 1] = temp;
            return i;
        }
    }
    return -1;
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given array []arr
    int []tempArr = { 2, 23, 14, 5,
                      6, 9, 8, 12 };
    Array arr = new Array(tempArr, 10, 8);
     
    Console.Write("Elements before Linear " +
                  "Search Transposition: ");
     
    // Function Call for displaying
    // the array []arr
    Display(arr);
     
    // Function Call for transposition
    LinearSearchTransposition(arr, 14);
     
    Console.Write("Elements after Linear " +
                  "Search Transposition: ");
     
    // Function Call for displaying
    // the array []arr
    Display(arr);
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program for transposition to
# improve the Linear Search Algorithm
 
 
# Structure of the array
class Array :
    def __init__(self,a=[0]*10,size=10,l=0) -> None:
        self.A=a
        self.size=size
        self.length=l
 
# Function to print array element
def Display(arr):
 
    # Traverse the array arr[]
    for i in range(arr.length) :
        print(arr.A[i],end=" ")
     
    print()
 
 
# Function that performs the Linear
# Search Transposition
def LinearSearchTransposition(arr, key):
 
    # Traverse the array
    for i in range(arr.length) :
 
        # If key is found, then swap
        # the element with it's
        # previous index
        if (key == arr.A[i]) :
 
            # If key is first element
            if (i == 0):
                return i
 
            arr.A[i],arr.A[i - 1]=arr.A[i - 1],arr.A[i]
 
            return i
         
     
    return -1
 
 
# Driver Code
if __name__ == '__main__':
    # Given array arr[]
    arr=Array([2, 23, 14, 5, 6, 9, 8, 12], 10, 8)
 
    print("Elements before Linear Search Transposition: ")
 
    # Function Call for displaying
    # the array arr[]
    Display(arr)
 
    # Function Call for transposition
    LinearSearchTransposition(arr, 14)
 
    print("Elements after Linear Search Transposition: ")
 
    # Function Call for displaying
    # the array arr[]
    Display(arr)

Mover al Frente/Cabeza :

En este método, si se encuentra el elemento clave, se intercambia directamente con el índice 0 , de modo que la siguiente vez consecutiva, la operación de búsqueda del mismo elemento clave sea de O(1) , es decir, tiempo constante. 

Por ejemplo: si la array arr[] es {2, 5, 7, 1, 6, 4, 5, 8, 3, 7} y la clave a buscar es 4, a continuación se muestran los pasos: 

• Después de buscar la clave 4 , el elemento se encuentra en el índice 5 de la array dada después de 6 comparaciones. Ahora, después de pasar a la operación frontal, la array se convierte en {4, 2, 5, 7, 1, 6, 5, 8, 3, 7}, es decir, la clave con valor 4 viene en el índice 0 .
• Nuevamente, después de buscar la clave 4 , el elemento se encuentra en el índice 0 de la array dada, lo que reduce el espacio de búsqueda completo.

// C program to implement the move to
// front to optimized Linear Search
#include <iostream>
using namespace std;
 
// Structure of the array
struct Array {
 
    int A[10];
    int size;
    int length;
};
 
// Function to print the array element
void Display(struct Array arr)
{
    int i;
 
    // Traverse the array arr[]
    for (i = 0; i < arr.length; i++) {
        cout <<" "<< arr.A[i];
    }
    cout <<"\n";
}
 
// Function that swaps two elements
// at different addresses
void swap(int* x, int* y)
{
    // Store the value store at
    // x in a variable temp
    int temp = *x;
 
    // Swapping of value
    *x = *y;
    *y = temp;
}
 
// Function that performs the move to
// front operation for Linear Search
int LinearSearchMoveToFront(
    struct Array* arr, int key)
{
    int i;
 
    // Traverse the array
    for (i = 0; i < arr->length; i++) {
 
        // If key is found, then swap
        // the element with 0-th index
        if (key == arr->A[i]) {
            swap(&arr->A[i], &arr->A[0]);
            return i;
        }
    }
    return -1;
}
 
// Driver code
int main()
{
    // Given array arr[]
    struct Array arr
        = { { 2, 23, 14, 5, 6, 9, 8, 12 },
            10,
            8 };
 
    cout <<"Elements before Linear"
           " Search Move To Front: ";
 
    // Function Call for displaying
    // the array arr[]
    Display(arr);
 
    // Function Call for Move to
    // front operation
    LinearSearchMoveToFront(&arr, 14);
 
    cout <<"Elements after Linear"
           " Search Move To Front: ";
 
    // Function Call for displaying
    // the array arr[]
    Display(arr);
    return 0;
}
 
// This code is contributed by shivanisinghss2110

// C program to implement the move to
// front to optimized Linear Search
#include <stdio.h>
 
// Structure of the array
struct Array {
 
    int A[10];
    int size;
    int length;
};
 
// Function to print the array element
void Display(struct Array arr)
{
    int i;
 
    // Traverse the array arr[]
    for (i = 0; i < arr.length; i++) {
        printf("%d ", arr.A[i]);
    }
    printf("\n");
}
 
// Function that swaps two elements
// at different addresses
void swap(int* x, int* y)
{
    // Store the value store at
    // x in a variable temp
    int temp = *x;
 
    // Swapping of value
    *x = *y;
    *y = temp;
}
 
// Function that performs the move to
// front operation for Linear Search
int LinearSearchMoveToFront(
    struct Array* arr, int key)
{
    int i;
 
    // Traverse the array
    for (i = 0; i < arr->length; i++) {
 
        // If key is found, then swap
        // the element with 0-th index
        if (key == arr->A[i]) {
            swap(&arr->A[i], &arr->A[0]);
            return i;
        }
    }
    return -1;
}
 
// Driver code
int main()
{
    // Given array arr[]
    struct Array arr
        = { { 2, 23, 14, 5, 6, 9, 8, 12 },
            10,
            8 };
 
    printf("Elements before Linear"
           " Search Move To Front: ");
 
    // Function Call for displaying
    // the array arr[]
    Display(arr);
 
    // Function Call for Move to
    // front operation
    LinearSearchMoveToFront(&arr, 14);
 
    printf("Elements after Linear"
           " Search Move To Front: ");
 
    // Function Call for displaying
    // the array arr[]
    Display(arr);
    return 0;
}

// Java program to implement
// the move to front to optimized
// Linear Search
class GFG{
 
// Structure of the array
static class Array
{
  int []A = new int[10];
  int size;
  int length;
  Array(int []A, int size,
        int length)
  {
    this.A = A;
    this.size = size;
    this.length = length;
  }
};
 
// Function to print the
// array element
static void Display(Array arr)
{
  int i;
 
  // Traverse the array arr[]
  for (i = 0;
       i < arr.length; i++)
  {
    System.out.printf("%d ", arr.A[i]);
  }
  System.out.printf("\n");
}
 
// Function that performs the
// move to front operation for
// Linear Search
static int LinearSearchMoveToFront(Array arr,
                                   int key)
{
  int i;
 
  // Traverse the array
  for (i = 0; i < arr.length; i++)
  {
    // If key is found, then swap
    // the element with 0-th index
    if (key == arr.A[i])
    {
      int temp = arr.A[i];
      arr.A[i] = arr.A[0];
      arr.A[0] = temp;
      return i;
    }
  }
  return -1;
}
 
// Driver code
public static void main(String[] args)
{
  // Given array arr[]
  int a[] = {2, 23, 14, 5,
             6, 9, 8, 12 };
  Array arr = new Array(a, 10, 8);
 
  System.out.printf("Elements before Linear" +
                    " Search Move To Front: ");
 
  // Function Call for
  // displaying the array
  // arr[]
  Display(arr);
 
  // Function Call for Move
  // to front operation
  LinearSearchMoveToFront(arr, 14);
 
  System.out.printf("Elements after Linear" +
                    " Search Move To Front: ");
 
  // Function Call for displaying
  // the array arr[]
  Display(arr);
}
}
 
// This code is contributed by gauravrajput1

// C# program to implement
// the move to front to optimized
// Linear Search
using System;
class GFG{
 
// Structure of the array
public class Array
{
  public int []A = new int[10];
  public int size;
  public int length;
  public Array(int []A,
               int size,
               int length)
  {
    this.A = A;
    this.size = size;
    this.length = length;
  }
};
 
// Function to print the
// array element
static void Display(Array arr)
{
  int i;
 
  // Traverse the array []arr
  for (i = 0;
       i < arr.length; i++)
  {
    Console.Write(" " + arr.A[i]);
  }
  Console.Write("\n");
}
 
// Function that performs the
// move to front operation for
// Linear Search
static int LinearSearchMoveToFront(Array arr,
                                   int key)
{
  int i;
 
  // Traverse the array
  for (i = 0; i < arr.length; i++)
  {
    // If key is found, then swap
    // the element with 0-th index
    if (key == arr.A[i])
    {
      int temp = arr.A[i];
      arr.A[i] = arr.A[0];
      arr.A[0] = temp;
      return i;
    }
  }
  return -1;
}
 
// Driver code
public static void Main(String[] args)
{
  // Given array []arr
  int []a = {2, 23, 14, 5,
             6, 9, 8, 12 };
   
  Array arr = new Array(a, 10, 8);
  Console.Write("Elements before Linear" +
                " Search Move To Front: ");
 
  // Function Call for
  // displaying the array
  // []arr
  Display(arr);
 
  // Function Call for Move
  // to front operation
  LinearSearchMoveToFront(arr, 14);
 
  Console.Write("Elements after Linear" +
                " Search Move To Front: ");
 
  // Function Call for displaying
  // the array []arr
  Display(arr);
}
}
 
// This code is contributed by gauravrajput1

# Python3 program for transposition to
# improve the Linear Search Algorithm
 
 
# Structure of the array
class Array :
    def __init__(self,a=[0]*10,size=10,l=0) -> None:
        self.A=a
        self.size=size
        self.length=l
 
# Function to print array element
def Display(arr):
 
    # Traverse the array arr[]
    for i in range(arr.length) :
        print(arr.A[i],end=" ")
     
    print()
 
 
# Function that performs the move to
# front operation for Linear Search
def LinearSearchMoveToFront(arr, key:int):
 
    # Traverse the array
    for i in range(arr.length) :
 
        # If key is found, then swap
        # the element with 0-th index
        if (key == arr.A[i]) :
            arr.A[i], arr.A[0]=arr.A[0],arr.A[i]
            return i
         
     
    return -1
 
 
# Driver Code
if __name__ == '__main__':
    # Given array arr[]
    arr=Array([2, 23, 14, 5, 6, 9, 8, 12], 10, 8)
 
    print("Elements before Linear Search Transposition: ",end='')
 
    # Function Call for displaying
    # the array arr[]
    Display(arr)
 
    # Function Call for transposition
    LinearSearchMoveToFront(arr, 14)
 
    print("Elements after Linear Search Transposition: ",end='')
 
    # Function Call for displaying
    # the array arr[]
    Display(arr)

Complejidad temporal: O(N)  
Espacio auxiliar : O(1)