INDEX
Ubiquitous Search Algorithm – Simple Search for Small Database
.
What is Ubiquitous?
The term “ubiquitous” means something that is present, found, or existing everywhere, or is very common and widely encountered.
It denotes a state of being omnipresent or pervasive in various places or contexts.
In other words, when something is described as ubiquitous, it is constantly or consistently present, often to the extent that it seems to be everywhere you look.
.
What is “Ubiquitous Search Algorithm”?
The term “Ubiquitous Search Algorithm” is not a standard or widely recognized algorithm in the field of computer science or data structures and algorithms. It is coined by Mark Weiser in 1988, as “Ubiquitous Computing” or “Ubicomp“, where computing is made to appear anytime and everywhere.
The “Ubiquitous Search Algorithm” would typically refer to a straightforward search method where you start searching from the beginning of a dataset, compare each element with the target you’re looking for, and continue until you find a match or reach the end of the dataset.
It’s a basic and common approach to searching and is often used when efficiency is not a primary concern, and simplicity is valued.
.
Algorithm of Ubiquitous Search Algorithm
1. Begin with a sorted Array.
2. Take two variables "low" and "High"
and place it to the array[0] and
array[n] respectively.
3. While (High - Low) > 1
4. Set mid = Low + (High - Low)/2
5. If (values[mid] <= Target Element)
6. Low = mid
7. Else
8. High = mid.
9.
10. If(value[Low] == Target Element)
11. print("Element found at value[Low]")
12. Else
13. print("Element not found")
.
Working of Ubiquitous Search
Sorted Array (Values) :- [3, 6, 9, 12, 15, 18, 21, 24, 27]
Target Element :-Â 18
Here’s the step-by-step dry run of the algorithm
Begin with a sorted array: [3, 6, 9, 12, 15, 18, 21, 24, 27]
Initialize two variables ‘Low’ and ‘High’ and place them at the beginning and end of the array.
Low = index 0 (points to the first element, which is 3)
High = index 8 (points to the last element, which is 27)
Check if (High – Low > 1). In this case, it is true.
.
Iteration 1
Mid = Low + (High – Low) / 2 = 0 + (8 – 0)/ 2 = 4
.
Check if values[mid] <= target element,
This is true because values[4] is 15, which is smaller than 18.
Update Low to be equal to mid (Low = mid = 4), so
Low = 4, and High = 8.
.
Iteration 2
Check if (High – Low == 1). In this case, it is true.
Calculate the midpoint:
Mid = Low + (High – Low) / 2 = 4 + (8 – 4)/ 2 = 6
.
Check if values[mid] <= target element,
This is true because values[6] is 21, which is greater than 18.
Update High to be equal to mid (High = mid = 6), so
Low = 4, and High = 6.
.
Iteration 3
Check if (High – Low == 1) is true. In this case, it is true.
Calculate the midpoint:
Mid = Low + (High – Low) / 2 = 4 + (6 – 4)/ 2 = 5
.
Check if values[mid] <= target element,
This is true because values[5] is 18, which is equal to 18.
Update Low to be equal to mid (Low = mid = 5), so Low becomes 5, and High is 6.
.
Iteration 4
Check if (High – Low == 1) is true. In this case, it is false.
Stop searching.
.
By Checking Value[Low] == 18, we conclude that “Element found at location 5. Successful Search.”
.
Source Code for Ubiquitous Search
#include <stdio.h>
int main()
{
   int n; // Number of elements in the array
   printf(“Enter the number of elements in the array: “);
   scanf(“%d”, &n);
   int values[n]; // Declare an array of size ‘n’
   printf(“Enter the sorted elements in the array:\n”);
   for (int i = 0; i < n; i++)
  {
       scanf(“%d”, &values[i]); // Input the sorted elements
   }
   int target; // Target element to search for
   printf(“Enter the target element to search for: “);
   scanf(“%d”, &target);
   int low = 0; // Initialize ‘Low’ to the beginning of the array
   int high = n – 1; // Initialize ‘High’ to the end of the array
   while (high – low > 1)
  {
       int mid = low + (high – low) / 2; // Calculate the midpoint
       if (values[mid] <= target)
    {
           low = mid; // Update ‘Low’ if the target is in the right half
       }
    else
    {
           high = mid; // Update ‘High’ if the target is in the left half
       }
   }
Â
   if (values[low] == target)
  {
       printf(“Element found at location %d\n”, low);
   }
  else
  {
       printf(“Element not found\n”);
   }
   return 0;
}
#include <iostream>
using namespace std;
int main()
{
   int n; // Number of elements in the array
   cout << “Enter the number of elements in the array: “;
   cin >> n;
   int values[n]; // Declare an array of size ‘n’
   cout << “Enter the sorted elements in the array:” << endl;
   for (int i = 0; i < n; i++)
  {
       cin >> values[i]; // Input the sorted elements
   }
   int target; // Target element to search for
   cout << “Enter the target element to search for: “;
   cin >> target;
   int low = 0; // Initialize ‘Low’ to the beginning of the array
   int high = n – 1; // Initialize ‘High’ to the end of the array
   while (high – low > 1)
  {
       int mid = low + (high – low) / 2; // Calculate the midpoint
       if (values[mid] <= target)
    {
           low = mid; // Update ‘Low’ if the target is in the right half
       }
    else
    {
           high = mid; // Update ‘High’ if the target is in the left half
       }
   }
Â
  if (values[low] == target)
  {
       cout << “Element found at location ” << low << endl;
   }
  else
  {
       cout << “Element not found” << endl;
   }
   return 0;
}
import java.util.Scanner;
public class UbiquitousSearch
{
   public static void main(String[] args)
  {
       Scanner scanner = new Scanner(System.in);
       // Input the number of elements in the array
       System.out.print(“Enter the number of elements in the array: “);
       int n = scanner.nextInt();
       int[] values = new int[n]; // Declare an array of size ‘n’
       // Input the sorted elements in the array
       System.out.println(“Enter the sorted elements in the array:”);
       for (int i = 0; i < n; i++)
    {
           values[i] = scanner.nextInt();
       }
       // Input the target element to search for
       System.out.print(“Enter the target element to search for: “);
       int target = scanner.nextInt();
       int low = 0; // Initialize ‘Low’ to the beginning of the array
       int high = n – 1; // Initialize ‘High’ to the end of the array
       while (high – low > 1)
    {
           int mid = low + (high – low) / 2; // Calculate the midpoint
           if (values[mid] <= target)
      {
               low = mid; // Update ‘Low’ if the target is in the right half
           }
      else
      {
               high = mid; // Update ‘High’ if the target is in the left half
           }
       }
Â
       if (values[low] == target)
    {
           System.out.println(“Element found at location ” + low);
       }
    else
    {
           System.out.println(“Element not found”);
       }
       scanner.close();
   }
}
def main():
   # Input the number of elements in the array
   n = int(input(“Enter the number of elements in the array: “))
Â
   # Input the sorted elements in the array
   values = [int(x) for x in input(“Enter the sorted elements in the array (space-separated): “).split()]
Â
Â
   # Input the target element to search for
   target = int(input(“Enter the target element to search for: “))
   low = 0 # Initialize ‘Low’ to the beginning of the array
   high = n – 1 # Initialize ‘High’ to the end of the array
Â
Â
   while high – low > 1:
       mid = low + (high – low) // 2 # Calculate the midpoint
       if values[mid] <= target:
           low = mid # Update ‘Low’ if the target is in the right half
       else:
           high = mid # Update ‘High’ if the target is in the left half
Â
Â
   if values[low] == target:
       print(f”Element found at location {low}”)
   else:
       print(“Element not found”)
if __name__ == “__main__”:
   main()
Time Complexity of Ubiquitous Search
The time complexity of the algorithm is O(log n) in the best, average, and worst cases.
.
Space Complexity of Ubiquitous Search
The space complexity is O(1), which means it uses a constant amount of extra space regardless of the size of the input dataset.
In the algorithm, you typically need only a few integer variables to keep track of indices (such as ‘low’ and ‘high’) and one or two additional variables for temporary storage (such as ‘mid’). These variables do not depend on the size of the dataset and therefore contribute to a constant amount of memory usage.
.
Applications of Ubiquitous Search
- Simple Data Lookup – Ubiquitous Search can be used in situations where you need to look up specific data items in a collection, such as searching for a contact in a phone book or finding a word in a dictionary.
- Database Queries – In database management systems, it can be employed for basic data retrieval tasks where the data is sorted, and an efficient, simple search is required.
- File Systems – Ubiquitous Search can be used within file systems to locate files or directories based on their names or attributes.
- Searching in Small Datasets – For relatively small datasets, where the overhead of more complex search algorithms is unnecessary, Ubiquitous Search can provide a quick and straightforward solution.
- Prototyping – During the development and prototyping phase of software projects, Ubiquitous Search can be used as a quick and simple solution for searching until more optimized approaches are implemented.
Test Yourself
Q1- Explain the concept of a Ubiquitous Search algorithm. When is it typically used, and what are its key characteristics?
The Ubiquitous Search algorithm is a basic search method that iterates through a sorted dataset, comparing each element with the target until a match is found or the end of the dataset is reached. It is used in situations where simplicity is valued over efficiency, such as searching in small datasets.
Key characteristics include simplicity, a time complexity of O(log n), and a constant space complexity of O(1).
Q2- What is the time complexity of the Ubiquitous Search algorithm, and under what conditions does it perform best and worst?
The time complexity of Ubiquitous Search is O(log n) in the best, average, and worst cases.
It performs best when the target element is in the middle of the dataset and worst when the target is either at the beginning or end.
Q3- How does the Ubiquitous Search algorithm differ from more efficient search algorithms like binary search? Provide a comparison of their time complexities.
Ubiquitous Search is a basic linear search algorithm. It iterates through a sorted dataset, comparing each element with the target until a match is found or the end of the dataset is reached. It does not require the dataset to be divided into halves unless 1st iteration. Binary search half the element in every search.
Binary search is preferred for large datasets, while Ubiquitous Search is suitable for small datasets or when simplicity is a priority.
Comparison of time complexities
Binary Search has O(1) time complexity in best search, whereas O(logn) time complexity for average and worst case.
Ubiquitous Search has O(logn) time complexity for best, average and worst case.
Q4- Can you provide a scenario where the Ubiquitous Search algorithm may not be suitable for searching? What are its limitations?
Ubiquitous Search is not suitable for large datasets or situations where efficiency is critical. It becomes impractical when the dataset is extremely large, as its time complexity of O(log n) can be significantly slower than more efficient search algorithms.
Q5- How does the Ubiquitous Search algorithm handle duplicate elements in the sorted dataset? Explain with an example.
Ubiquitous Search will find the first occurrence of a duplicate element. If there are multiple duplicates, it will not find the subsequent occurrences.
For example, if the dataset is [1, 2, 2, 3, 4] and the target is 2, Ubiquitous Search will return the index 2, which is the first occurrence of 2 as mid calculates to index 2.
Q6- What is the primary advantage of using the Ubiquitous Search algorithm?
Fastest search algorithm
Simplicity and ease of implementation
Low memory usage
Always finds the target element
Ans – (2)
Explanation – The primary advantage of Ubiquitous Search is its simplicity and ease of implementation.
Q7- When does the Ubiquitous Search algorithm perform best in terms of search time?
When the target is at the beginning of the dataset
When the target is at the end of the dataset.
When the target is in the middle of the dataset
When the target is in the array.
Ans – (4)
Explanation – When the target is in the dataset, because in best case, average case or worst case, we find no difference in the time complexity. But if the target is not in the dataset, then we have to perform 1 extra operation.Â
Q8- Which of the following is a limitation of the Ubiquitous Search algorithm?
It is memory-intensive.
It cannot handle sorted datasets.
It is not suitable for large datasets.
It has a time complexity of O(1).
Ans – (3)
Explanation – It is not suitable for large datasets.
Q9- Using the Ubiquitous Search algorithm, if you have the following sorted input array: [2, 2, 2, 2, 2, 2, 2], and you’re searching for the target element 2, what would be the output index when the search is performed?
In the Ubiquitous Search algorithm, when searching for the target element 2 in the input array [2, 2, 2, 2, 2, 2, 2], the algorithm will find the last occurrence of the target element.
Â
Explanation –
Begin with a sorted array: [2, 2, 2, 2, 2, 2, 2].
Initialize ‘Low’ to the beginning of the array (Low = 0) and ‘High’ to the end of the array (High = 6).
Calculate the midpoint: Mid = Low + (High – Low) / 2 = 0 + (6 – 0) / 2 = 3.
Check if values[Mid] (values[3]) is less than or equal to the target (2). This is true.
Update ‘Low’ to be equal to Mid (Low = 3).
.
Repeat the process:
Calculate the midpoint: Mid = Low + (High – Low) / 2 = 3 + (6 – 3) / 2 = 4.
Check if values[Mid] (values[4]) is less than or equal to the target (2). This is true.
Update ‘Low’ to be equal to Mid (Low = 4).
Calculate the midpoint: Mid = Low + (High – Low) / 2 = 4 + (6 – 4) / 2 = 5.
Check if values[Mid] (values[5]) is less than or equal to the target (2). This is true.
Update ‘Low’ to be equal to Mid (Low = 5).
Now, High – Low = 1, so we stop searching.
Check if values[Low] (values[6]) is equal to the target (2). This is true.
Therefore, the Ubiquitous Search algorithm will find the last occurrence of the target element 2, and the output index will be index 5.
Â
