Searching in Data Structure

Last Updated on January 25, 2023 by Prepbytes

In this article, we are going to discuss what is searching in Data structure.

What is Searching in Data Structure?

The process of finding desired information from a set of elements stored in the form of elements in a computer’s memory is called "searching data structures". These sets of elements have various forms, including: As an array, tree, chart, or linked list. Another way to define a search in a data structure is to find a desired element with certain characteristics within a collection of elements.

Search Methods

Searching within a data structure can be performed by implementing a search algorithm that finds or retrieves elements in any form of the stored data structure. These algorithms are categorized based on the type of search operation, such as:

1. Sequential Search: An array or list of elements is traversed sequentially, examining each component of the set. Ex. Linear Search
2. Interval Search: Algorithms designed explicitly for searching sorted data structures are included in interval search. The efficiency of these algorithms is much better than linear search algorithms. For example, binary search, logarithmic search.

These methods are investigated based on the time it takes the algorithm to find items matching the search term in the data collection.

Let’s Discuss Linear Search and Binary Search in detail.

Linear Search:

Linear search is the simplest searching technique in which the elements of the array are compared one by one with the search element. The time complexity of the linear search is O(n), where n is the number of elements in the array. The following is an example of linear search in C++:

#include <iostream>
using namespace std;

int linearSearch(int arr[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) {
            return i;
        }
    }
    return -1;
}

int main() {
    int arr[] = {1, 10, 30, 15, 20};
    int x = 30;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = linearSearch(arr, n, x);
    if (result == -1) {
        cout << "Element not found" << endl;
    } else {
        cout << "Element found at index " << result << endl;
    }
    return 0;
}

Output:

Element found at index 2

In the above example, the function linearSearch() takes in an array, its size, and the element to be searched as input and returns the index of the element if found, otherwise -1.
The linear search algorithm in C++ starts by declaring a function called linearSearch() which takes in three parameters: an array, an integer n representing the size of the array, and an integer x representing the element to be searched for. Inside the function, we use a for loop to iterate through the array, starting from index 0 and ending at index n-1. Within the for loop, we use an if statement to compare each element of the array with the search element x. If a match is found, the function returns the index of the element in the array. If the element is not found in the array, the function returns -1.

The main() function initializes an array of integers, assigns the value of 30 to the variable x, and calculates the size of the array using the sizeof() function. The linearSearch() function is then called, passing in the array, its size, and the search element as arguments. The result of the function is stored in a variable called result. An if-else statement is then used to check if the result is -1 or not. If the result is -1, the program prints "Element not found", otherwise it prints "Element found at index" followed by the value of the result.

The time complexity of this linear search algorithm is O(n), where n is the number of elements in the array. This means that the algorithm takes linear time to run and its performance will degrade as the number of elements in the array increases. This makes it less efficient than other searching algorithms such as binary search, which has a time complexity of O(log n) and performs better with large arrays.

Binary Search:

Binary search is an efficient algorithm for finding an element in a sorted array. The basic idea is to divide the array in half repeatedly until the desired element is found. Here’s an example implementation in C++:

#include <iostream>

int binarySearch(int arr[], int n, int x) {
    int left = 0;
    int right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == x) {
            return mid;
        } else if (arr[mid] < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 10;
    int result = binarySearch(arr, n, x);
    if (result == -1) {
        std::cout << "Element not present in array" << std::endl;
    } else {
        std::cout << "Element found at index: " << result << std::endl;
    }
    return 0;
}

Output

Element found at index: 3

The function binarySearch takes in an array, its size, and the element to be searched (x) as input. It initializes two variables left and right to the first and last indices of the array, respectively. It then enters a while loop that continues until left is less than or equal to right.

Inside the while loop, the middle index is calculated as the average of the left and right indices. The element at the middle index is compared to the target element (x). If they are equal, the function returns the middle index as the result. If the element at the middle index is less than x, it means the target element must be in the right half of the array, so the left index is updated to be one greater than the middle index. If the element at the middle index is greater than x, it means the target element must be in the left half of the array, so the right index is updated to be one less than the middle index.

If the while loop completes and the target element is not found, the function returns -1 to indicate that the element is not present in the array.

In the main function, an array is defined, and the binarySearch function is called with this array, its size, and the target element as input. The result of the function is checked, and a message is printed indicating whether the element was found or not.

Conclusion
In this article, we have discussed what is searching in data structure and then learned what searching methods are. On the basis of searching methods, we also discussed, two searching algorithms first Linear search, and the second one was Binary search.