Reasignación de elementos en base a la Localidad de Referencia

Considere un problema en el que es probable que se busquen los mismos elementos una y otra vez. Implementar la operación de búsqueda de manera eficiente. 
Ejemplos: 
 

Input : arr[] = {12 25 36 85 98 75 89 15 63 66
                               64 74 27 83 97}
          q[] = {63, 63, 86, 63, 78}
Output : Yes Yes No Yes No
We need one by one search items of q[] in arr[].
The element 63 is present, 78 and 86 are not present.

La idea es simple , movemos el elemento buscado al frente de la array para que pueda buscarse rápidamente la próxima vez. 
 

// C++ program to implement search for an item
// that is searched again and again.
#include <bits/stdc++.h>
using namespace std;
 
// A function to perform sequential search.
bool search(int arr[], int n, int x)
{
    // Linearly search the element
    int res = -1;
    for (int i = 0; i < n; i++)
        if (x == arr[i])
        res = i;
 
    // If not found
    if (res == -1)
        return false;
 
    // Shift elements before one position
    int temp = arr[res];
    for (int i = res; i > 0; i--)
        arr[i] = arr[i - 1];
 
    arr[0] = temp;
    return true;
}
 
// Driver Code
int main()
{
    int arr[] = { 12, 25, 36, 85, 98, 75, 89, 15,
                    63, 66, 64, 74, 27, 83, 97 };
    int q[] = {63, 63, 86, 63, 78};
    int n = sizeof(arr)/sizeof(arr[0]);
    int m = sizeof(q)/sizeof(q[0]);
    for (int i=0; i<m; i++)
    search(arr, n, q[i])? cout << "Yes "
                        : cout << "No ";    
 
    return 0;
}

// Java program to implement search for an item
// that is searched again and again.
import java.util.*;
 
class solution
{
 
// A function to perform sequential search.
static boolean search(int[] arr, int n, int x)
{
    // Linearly search the element
    int res = -1;
    for (int i = 0; i < n; i++)
        if (x == arr[i])
        res = i;
 
    // If not found
    if (res == -1)
        return false;
 
    // Shift elements before one position
    int temp = arr[res];
    for (int i = res; i > 0; i--)
        arr[i] = arr[i - 1];
 
    arr[0] = temp;
    return true;
}
 
// Driver Code
public static void main(String args[])
{
    int []arr = { 12, 25, 36, 85, 98, 75, 89, 15,
                    63, 66, 64, 74, 27, 83, 97 };
    int []q = {63, 63, 86, 63, 78};
    int n = arr.length;
    int m = q.length;
    for (int i=0; i<m; i++)
    {
    if(search(arr, n, q[i]) == true)
        System.out.print("Yes ");
    else
        System.out.print("No ");
    }
}
}
// This code is contributed by
// Shashank_Sharma

# Python 3 program to implement search for
# an item that is searched again and again.
 
# A function to perform sequential search.
def search(arr, n, x):
     
    # Linearly search the element
    res = -1
    for i in range(0, n, 1):
        if (x == arr[i]):
            res = i
 
    # If not found
    if (res == -1):
        return False
 
    # Shift elements before
    # one position
    temp = arr[res]
    i = res
    while(i > 0):
        arr[i] = arr[i - 1]
        i -= 1
 
    arr[0] = temp
    return True
 
# Driver Code
if __name__ == '__main__':
    arr = [12, 25, 36, 85, 98, 75, 89,
           15, 63, 66, 64, 74, 27, 83, 97]
    q = [63, 63, 86, 63, 78]
    n = len(arr)
    m = len(q)
    for i in range(0, m, 1):
        if(search(arr, n, q[i])):
            print("Yes", end = " ")
        else:
            print("No", end = " ")
 
# This code is contributed by
# Surendra_Gangwar

// C# program to implement search for an
// item that is searched again and again.
using System;
 
class GFG
{
     
// A function to perform sequential search.
static bool search(int[] arr, int n, int x)
{
    // Linearly search the element
    int res = -1;
    for (int i = 0; i < n; i++)
        if (x == arr[i])
        res = i;
 
    // If not found
    if (res == -1)
        return false;
 
    // Shift elements before one position
    int temp = arr[res];
    for (int i = res; i > 0; i--)
        arr[i] = arr[i - 1];
 
    arr[0] = temp;
    return true;
}
 
// Driver Code
public static void Main()
{
    int[] arr = { 12, 25, 36, 85, 98, 75, 89, 15,
                      63, 66, 64, 74, 27, 83, 97 };
    int[] q = {63, 63, 86, 63, 78};
    int n = arr.Length;
    int m = q.Length;
    for (int i = 0; i < m; i++)
    {
        if(search(arr, n, q[i]) == true)
            Console.Write("Yes ");
        else
            Console.Write("No ");
    }
}
}
 
// This code is contributed by
// Akanksha Rai

<?php
// PHP program to implement search for an
// item that is searched again and again.
 
// A function to perform sequential search.
function search($arr, $n, $x)
{
    // Linearly search the element
    $res = -1;
    for ($i = 0; $i < $n; $i++)
        if ($x == $arr[$i])
        $res = $i;
 
    // If not found
    if ($res == -1)
        return false;
 
    // Shift elements before one position
    $temp = $arr[$res];
    for ($i = $res; $i > 0; $i--)
        $arr[$i] = $arr[$i - 1];
 
    $arr[0] = $temp;
    return true;
}
 
// Driver Code
$arr = array(12, 25, 36, 85, 98, 75, 89, 15,
                 63, 66, 64, 74, 27, 83, 97);
$q = array(63, 63, 86, 63, 78);
$n = sizeof($arr);
$m = sizeof($q);
 
for ($i = 0; $i < $m; $i++)
    if(search($arr, $n, $q[$i]))
        echo "Yes ";
    else
        echo "No ";    
 
// This code is contributed
// by Akanksha Rai

<script>
// Javascript program to implement search for an item
// that is searched again and again.
 
// A function to perform sequential search.
function search(arr, n, x)
{
    // Linearly search the element
    let res = -1;
    for (let i = 0; i < n; i++)
        if (x == arr[i])
        res = i;
 
    // If not found
    if (res == -1)
        return false;
 
    // Shift elements before one position
    let temp = arr[res];
    for (let i = res; i > 0; i--)
        arr[i] = arr[i - 1];
 
    arr[0] = temp;
    return true;
}
 
// Driver Code
 
    let arr = [ 12, 25, 36, 85, 98, 75, 89, 15,
                    63, 66, 64, 74, 27, 83, 97 ];
    let q = [63, 63, 86, 63, 78];
    let n = arr.length;
    let m = q.length;
    for (let i=0; i<m; i++)
    search(arr, n, q[i])? document.write("Yes ")
                        : document.write("No ");   
                         
   // This code is contributed by _saurabh_jaiswal.                    
</script>

Producción: 
 

Yes Yes No Yes No 

Pensamientos adicionales: Podemos hacerlo mejor usando una lista enlazada. En la lista enlazada, se puede mover un elemento al frente en tiempo O(1). 
La mejor solución sería usar Splay Tree (una estructura de datos diseñada para este propósito). Splay Tree admite operaciones de inserción, búsqueda y eliminación en tiempo O (Inicio de sesión) en promedio. Además, splay tree es un BST, por lo que podemos imprimir elementos rápidamente en orden.