OOP design for Search Algorithms

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

In this article, we have presented good implementation designs considering there are multiple search algorithms and different data types.

Introduction

Search algorithms are used to find and retrieve information from a database. They are an essential component of modern computer science and are widely used in many applications, such as web search engines, online shopping, and recommendation systems.

Search algorithms can be classified based on their complexity, efficiency, and the types of data we have to search through. Commonly used seaarching algorithms include linear search, binary search, hashset, BFS, DFS, A*. In addition to the algorithm's efficiency, the design of the algorithm is also essential.

What is Object-Oriented Programming (OOP)?
Object-Oriented Programming (OOP) is a popular paradigm used in software development that focuses on the design and organization of code into classes and objects.

Object-oriented programming (OOP) design is an effective way to develop search algorithms because it allows for modularity, encapsulation, and extensibility. In this article, we will discuss the design principles of search algorithms using OOP and examine how different search algorithms can be chosen according to the specific requirements of an array.

Overview of Searching Algorithms

Linear Search
Idea : It is a simple method for finding an element in an array by scanning each element sequentially until the target element is found.
The pros of sequential search are that it works on any type of array and does not require the array to be sorted.
The cons are that it has a worst-case time complexity of O(n), where n is the number of elements in the array.
Approach: The algorithm starts at the beginning of the array and compares each element with the target element until a match is found.

Binary Search
Idea : Binary search is a more efficient search algorithm than sequential search, but it requires the array to be sorted.
The pros of binary search are that it has a worst-case time complexity of O(log n), where n is the number of elements in the array, and it is more efficient than sequential search.
The cons are that it only works on sorted arrays and requires more memory than sequential search.
Approach : The algorithm divides the array in half and compares the target element with the middle element. If the target element is greater than the middle element, the algorithm searches the right half of the array. If the target element is smaller than the middle element, the algorithm searches the left half of the array. The algorithm continues to divide the array in half and compare the target element with the middle element until the target element is found or the search range is empty.

HashSet
HashSet is a collection that contains unique elements. It does not maintain the order of the elements. To perform a linear search in a HashSet, we can iterate over the elements using an iterator and compare each element with the target element until a match is found. The time complexity of a linear search in a HashSet is O(n) in the worst case.

BFS
BFS or Breadth-First Search is a graph traversal algorithm that visits all the vertices of a graph in breadth-first order. To perform a linear search using BFS, we can start the traversal from the source vertex and check each vertex until we find the target vertex. The time complexity of a linear search using BFS is O(V+E), where V is the number of vertices and E is the number of edges in the graph.

DFS
DFS or Depth-First Search is another graph traversal algorithm that visits all the vertices of a graph in depth-first order. To perform a linear search using DFS, we can start the traversal from the source vertex and recursively visit each vertex until we find the target vertex. The time complexity of a linear search using DFS is O(V+E), where V is the number of vertices and E is the number of edges in the graph.

A search*
A* or A-star is a heuristic search algorithm that is commonly used in path finding and graph traversal. To perform a linear search using A*, we can use a heuristic function to estimate the distance from each vertex to the target vertex and prioritize the vertices to visit based on their estimated distance. The time complexity of a linear search using A* depends on the complexity of the heuristic function and the number of vertices in the graph.

In summary, the selection of a search algorithm relies on various factors, such as the size and nature of the dataset being searched, the desired speed and accuracy, and the available memory resources.

CHOOSING THE BEST SEARCHING ALGORITHM ACCORDING TO ARRAY

Factors to consider when choosing a search algorithm:

Is the data sorted or unsorted?
Is the data ordered or unordered?
Is the data structured as a graph or a list or an array?
Are we searching for a single element or a range of elements?

Based on the characteristics of the data and the requirements of the problem, one of the following search algorithms may be more used:

AlgorithmTime ComplexitySpace ComplexityData StructureKey AdvantagesKey Disadvantages
Linear SearchO(n)O(1)Array/ ListSimple to implement, works with unsorted dataSlow for large data sets
Binary SearchO(logn)O(1)Sorted ArrayEfficient for large data sets, only requires sorted dataRequires a sorted array, not applicable for unsorted data
HashsetO(1)O(n)Hash TableFast lookup for individual elementsNot suitable for ordered data or range queries
Breadth- First Search (BFS)O(V + E)O(V)GraphGuarantees shortest path for unweighted graphsMemory intensive for large graphs
Depth-First Search (DFS)O(V + E)O(V)GraphMemory efficient, useful for finding paths in a graphDoes not guarantee shortest path
A* SearchO(b^d)O(b^d)Array/ ListEfficient for finding shortest paths in weighted graphsRequires a heuristic function, not always optimal

CHOOSING THE BEST SEARCHING ALGORITHM ACCORDING TO ARRAY SIZE

Length of InputPreferred Searching AlgorithmReasoning
Small (less than 10 elements)Linear SearchFor small input sizes, linear search is often the simplest and most efficient algorithm.
Medium (between 10 and 1000 elements)Binary SearchFor medium-sized input data that is sorted, binary search is often the most efficient algorithm.
Large (more than 1000 elements)HashsetFor large input data, a hashset can provide fast constant-time lookups, making it an efficient algorithm.
Graph Search (pathfinding, network analysis)A* Search or BFSFor graph search problems where finding the shortest path is important, A* search or BFS are often the preferred algorithms. The choice depends on the characteristics of the graph, such as its size, shape, and weights.
Tree Search (finding nodes in a tree)DFSFor tree search problems, DFS is often the preferred algorithm, as it is efficient and easy to implement. However, if the tree is very deep, BFS may be a better option to avoid running out of memory.

OOP Design for Search Algorithms with Java Implementation using a Generic Array Class

To design a search algorithm using object-oriented programming (OOP) principles and Java language, we can do the following implementation:

Define the Generic Array Class:

public class GenericArray<T> {
    private T[] array;
    private int size;
    
    public GenericArray(int capacity) {
        array = (T[]) new Object[capacity];
        size = 0;
    }
    
    public void add(T element) {
        array[size++] = element;
    }
    
    public int length() {
        return size;
    }
    
    public T get(int index) {
        if (index >= size) {
            throw new IndexOutOfBoundsException("Index out of range!");
        }
        return array[index];
    }
}

Define the Search Algorithm Interface:
We will define an interface for the search algorithm that will be implemented by various search algorithms like Linear Search, Binary Search, etc. This interface will have the following method:

A public method that takes the array and the element to be searched as input and returns the index of the element if found, or -1 if not found.

The Java implementation for this interface is shown below:

public interface SearchAlgorithm<T> {
    public int search(GenericArray<T> array, T key);
}

Linear Search

public class LinearSearch<T> implements SearchAlgorithm<T> {
    public int search(GenericArray<T> array, T key) {
        for (int i = 0; i < array.length(); i++) {
            if (array.get(i).equals(key)) {
                return i;
            }
        }
        return -1;
    }
}

Binary Search

public class BinarySearch<T extends Comparable<T>> {
    public static <T extends Comparable<T>> int search(GenericArray<T> array, T key) {
        int left = 0;
        int right = array.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            int cmp = key.compareTo(array.get(mid));
            if (cmp < 0) {
                right = mid - 1;
            } else if (cmp > 0) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

Trie Search

public class TrieSearch implements SearchAlgorithm<String> {
    public int search(GenericArray<String> array, String key) {
        Trie trie = new Trie();
        for (int i = 0; i < array.length(); i++) {
            trie.insert(array.get(i));
        }
        return trie.search(key);
    }
}

Main Example

GenericArray<String> array = new GenericArray<>(5);
array.add("apple");
array.add("banana");
array.add("orange");
array.add("mango");
array.add("kiwi");

int index = LinearSearch.search(array, "banana");
System.out.println("Linear search found banana at index " + index);

index = BinarySearch.search(array, "mango");
System.out.println("Binary search found mango at index " + index);

index = TrieSearch.search(array, "kiwi");
System.out.println("Trie search found kiwi at index " + index);

Output:

Linear search found banana at index 1
Binary search found mango at index 3
Trie search found kiwi at index 4

Understanding the OOP design

The above code demonstrates the Object-Oriented Programming (OOP) principles of Encapsulation, Inheritance, Polymorphism, and Abstraction.
We have above used a generic array class to hold any type of data, and then implements two types of search algorithms: linear search and binary search.

Linear search checks each element in the array one by one until it finds the desired element or reaches the end of the array.

Binary search, on the other hand, requires the array to be sorted first. It then repeatedly divides the search interval in half until the desired element is found or the interval becomes empty.

Encapsulation
Encapsulation is the practice of hiding the implementation details of an object from external classes, and providing a simple and secure interface for accessing its functionality.
In the code above, the GenericArray class encapsulates the implementation details of an array data structure, and ensures that the internal implementation is hidden from external classes. It also prevents direct access to the underlying array by providing access only through its public methods.

Inheritance
Inheritance is the mechanism of creating new classes that inherit properties and methods from existing classes, and extend or modify their behavior. In the code above, the BinarySearch class extends the Comparable interface to ensure that the elements in the array can be compared. This allows the binary search algorithm to work with any data type that implements the Comparable interface, without having to rewrite the code for each type.

Polymorphism
Polymorphism is the ability of objects of different classes to be treated as if they are of the same class, as long as they have the same methods or properties. In the code above, both the LinearSearch and BinarySearch classes implement a search method, but they have different implementations. This is an example of polymorphism, which allows objects of different classes to be treated in the same way when calling the search method.

Abstraction
Abstraction is the practice of providing a simple and consistent interface for working with complex objects or systems, and hiding the complexity of their implementation. In the code above, the GenericArray class provides a simple interface for working with arrays, abstracting away the details of how the array is implemented. This abstraction allows us to work with arrays at a higher level of abstraction, without worrying about the details of their implementation.

Conclusion

The above code demonstrates the powerful and flexible nature of Object-Oriented Programming (OOP) principles. By using Encapsulation, Inheritance, Polymorphism, and Abstraction, we can create more modular, reusable, and flexible code that is easier to extend and maintain.

  • Encapsulation helps to hide the implementation details of objects from external classes, promoting security and simplicity.
  • Inheritance allows us to extend and modify the behavior of existing classes, making code more flexible and reusable.
  • Polymorphism enables objects of different classes to be treated in the same way, promoting code reusability and maintainability.
  • Abstraction allows us to work with complex objects or systems at a higher level of abstraction, hiding their implementation details and promoting separation of concerns.

In conclusion, the OOP design for Search Algorithms demonstrated how to use OOP principles to create more modular, reusable, and flexible search algorithms. By applying Encapsulation, Inheritance, Polymorphism, and Abstraction, we can create code that is easier to extend and maintain, and build more complex systems with less effort.

Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS.