Consider a problem where same elements are likely to be searched again and again. Implement search operation efficiently.
Examples :
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.
Implementation: The idea is simple, we move the searched element to front of the array so that it can be searched quickly next time.
C++
// 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 Codeint 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
// 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 Codepublic 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 |
Python3
# 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 Codeif __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#
// 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 Codepublic 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// 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 |
Javascript
<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> |
Output
Yes Yes No Yes No
Complexity Analysis:
- Time Complexity : O(m*n)
- Space Complexity : O(1)
Further Thoughts : We can do better by using a linked list. In linked list, moving an item to front can be done in O(1) time.
The best solution would be to use Splay Tree (a data structure designed for this purpose). Splay tree supports insert, search and delete operations in O(Log n) time on average. Also, splay tree is a BST, so we can quickly print elements in sorted order.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
