Search forward and backward in unsorted array

Unsorted Array - An array is a data structure consisting of a collection of elements of the same type. An unsorted array is a structure in which the order of elements is random, i.e. on insertion, the element is added to the last element regardless of the order of the previous elements, and searching in such an array does not suffer any Search algorithms help because of the lack of element positioning patterns.

Search - Searching in an array means finding a specific element in the array, which can return the position of the desired element or a bool statement specifying whether the element is present in the array or no.

• Searching ahead - Searching ahead of an array means doing a linear search traversal of the array starting from the 0th index (i.e. the first element).

• Reverse search - Reverse search of an array means a linear search traversal of the array starting from the (n-1)th index (i.e. the last element).

Problem Statement

Given a search element x, find whether x exists in the following situations -

• Arrays with elements of the same size, integer arrays.

• Arrays with elements of different sizes, string arrays.

Example 1

Input: x = 4, [6, 1, 4, 10, 2]

Output: TRUE

Explanation - In the given array, 4 occurs at the second index.

Example 2

Input: x = “high”, [“goat”, “ice”, “hgh”]

Output: False

Explanation - In the given array, "high" does not exist.

solution

As mentioned above, forward search starts from the first element and backward search starts from the last element. Combining these two methods, the time of searching for an element in the array can be reduced by twice since the first and second half of the array are checked simultaneously.

To find whether an element appears in an array, define first and last as the first and last elements of the array. Returns true if either the first or last element is the required element, otherwise increments the first element by 1, decrements the last element by 1, and continues until the element is found. If first and last are equal when the traversal is completed, then false is returned if the element is not found.

pseudocode

procedure frontBack (arr[], x)
   first = 0
   last = n - 1
   while first <= last
      If arr[first] == x or arr[last] == x
         ans = true
       end if
      front = front + 1
      last = last - 1
   ans = false
end procedure

Example: C implementation

In the following program, we take the first case of integer array. Get the first and next variables while checking the first and last elements to find the required element. If the element is found, return true, otherwise go to the next element and check again.

#include <bits/stdc++.h>
using namespace std;
// Function to front back search an element in the array
bool frontBack(int arr[], int x){
   int first = 0, last = 9;
   
   // loop execute till the element is found or traversal completes
   while (first <= last){
      if (arr[first] == x || arr[last] == x){
         return true;
      }
      first++;  // Incrementing first
      last--;  // Decrementing last
   }
   return false;
}
int main(){
   int arr[10] = {21, 43, 10, 19, 3, 56, 91, 20, 5, 79};
   int x = 55;
   cout << "In the array : ";
   for (int i = 0; i < 10; i++){
      cout << arr[i] << " ";
   }
   cout << "\nElement " << x;
   if (frontBack(arr, x)){
      cout << " is present.";
   }
   else{
      cout << " is not present.";
   }
   return 0;
}

Output

In the array : 21 43 10 19 3 56 91 20 5 79 
Element 55 is not present.

Time complexity - O(n/2), since searching from both sides cuts the time in half.

Space complexity - O(1)

Example

In the following program, we use the second case of string array. Get the first and next variables while checking the first and last elements to find the required element. If the element is found, return true, otherwise go to the next element and check again.

#include <bits/stdc++.h>
using namespace std;
// Function to front back search an element in the array
bool frontBack(string arr[], string x){
   int first = 0, last = 9;
   
   // loop execute till the element is found or traversal completes
   while (first <= last)    {
      if (arr[first] == x || arr[last] == x)        {
         return true;
      }
      first++; // Incrementing first
      last--; // Decrementing last
   }
   return false;
}
int main(){
   string arr[4] = {"hi", "high", "goat", "goa"};
   string x = "goat";
   cout << "In the array : ";
   for (int i = 0; i < 4; i++) {
      cout << arr[i] << ", ";
   }
   cout << "\nElement " << x;
   if (frontBack(arr, x)) {
      cout << " is present.";
   }
   else {
      cout << " is not present.";
   }
   return 0;
}

Output

In the array : hi, high, goat, goa, 
Element goat is present.

Time complexity - O(n/2), since searching from both sides cuts the time in half.

Space complexity - O(1)

in conclusion

In short, the forward and backward search of the array is similar to the usual linear search, except that it checks two elements at the same time, thus reducing the time consumption by half. This transforms the worst-case time complexity of searching in an unsorted array from O(n) to O(n/2).

The above is the detailed content of Search forward and backward in unsorted array. For more information, please follow other related articles on the PHP Chinese website!