Searching in Data Structures - Its Types, Methods & Techniques

Searching in Data Structures: An Overview

In this DSA tutorial, we are going to understand searching, its features, various types of searching algorithms, etc. To further enhance your understanding and application of search concepts, consider enrolling in the Dsa Course Online, where you can gain comprehensive insights into effective data structure utilization for improved problem-solving and time management.

What is Searching in Data Structures?

The goal is to find the desired information with its precise location quickly and with minimal computational resources. It plays an important role in various computational tasks and real-world applications, including information retrieval, data analysis, decision-making processes, etc.

Characteristics of Searching

• Target Element/Key: It is the element or item that you want to find within the data collection. This target could be a value, a record, a key, or any other data entity of interest.
• Search Space: It refers to the entire collection of data within which you are looking for the target element. Depending on the data structure used, the search space may vary in size and organization.
• Complexity: Searching can have different levels of complexity depending on the data structure and the algorithm used. The complexity is often measured in terms of time and space requirements.
• Deterministic vs. Non-deterministic: The algorithms that follow a clear, systematic approach, like binary search, are deterministic. Others, such as linear search, are non-deterministic, as they may need to examine the entire search space in the worst case.

Searching Algorithms in Data Structures

1. Linear search: This is the most simple searching algorithm in the data structures that checks each element of the data structure until the desired element is found.

   We will see this algorithm in the next tutorial, Linear Search in Data Structures

2. Binary search: This algorithm is used for searching in a sorted array or list. It works by repeatedly dividing the search interval in half until the desired element is found or the search interval is empty.

   We will see this algorithm in detail in Binary Search in Data Structures

3. Interpolation Search: Similar to binary search, interpolation search works on sorted lists. Instead of always dividing the search range in half, interpolation search uses the value of the target element and the values of the endpoints to estimate its approximate position within the list. This estimation helps in quickly narrowing down the search space.
4. Fibonacci Search: It uses Fibonacci numbers to divide the search space. It works on sorted arrays and has a similar approach to binary search, but instead of dividing the array into halves, it divides it into two parts using Fibonacci numbers as indices.
5. Exponential Search: It is a searching algorithm designed to find a target value in a sorted collection, such as an array or list. It combines elements of Binary Search and Linear Search to efficiently locate the target, especially when its position is near the beginning of the collection.
6. Ternary Search: It divides the search space into three parts instead of two based on two splitting points. It is a divide-and-conquer approach that operates on sorted lists.
7. Jump Search: Jump Search can be used on sorted collections (arrays or lists). The idea is to reduce the number of comparisons by jumping ahead by fixed steps or skipping some elements in place of searching for all elements.

Read More - Data Structure Interview Questions for Freshers

Searching Techniques: Linear Search and Binary Search

Linear Search

1. Start at the beginning of the list.
2. Compare the target value with the current element in the list.
3. If the current element matches the target value, the search is successful, and the position or index of the element is returned.
4. If the current element does not match the target value, move to the next element in the list.
5. Repeat steps 2-4 until a match is found or the end of the list is reached.
6. If the end of the list is reached without finding a match, the search is unsuccessful, and a special value (e.g., -1) may be returned to indicate the absence of the target value

Pseudocode for Linear Search Algorithm

LinearSearch(array, target): 
for each element in array, from left to right:
 if element equals target:
 return index of element
 return -1 // target not found in the array

Example of Linear Search

num = 5

arr = [10, 20, 30, 40, 50]

search = 30

found = False

for cnt in range(num):
    if arr[cnt] == search:
        print(f"{search} is present at location {cnt + 1}.")
        found = True
        break

if not found:
    print(f"{search} is not present in the array.")
    

class LinearSearch {
    public static void main(String[] args) {
        int num = 5;
        int[] arr = {10, 20, 30, 40, 50};
        int search = 30;
        boolean found = false;

        for (int cnt = 0; cnt < num; cnt++) {
            if (arr[cnt] == search) {
                System.out.println(search + " is present at location " + (cnt + 1) + ".");
                found = true;
                break;
            }
        }

        if (!found) {
            System.out.println(search + " is not present in the array.");
        }
    }
}
    

#include <iostream>
using namespace std;

int search(int array[], int n, int key) {
    for (int i = 0; i < n; i++)
        if (array[i] == key)
            return i;
    return -1;
}

int main() {
    int num = 5;
    int arr[] = {10, 20, 30, 40, 50};
    int search = 30;
    bool found = false;

    for (int cnt = 0; cnt < num; cnt++) {
        if (arr[cnt] == search) {
            cout << search << " is present at location " << (cnt + 1) << "." << endl;
            found = true;
            break;
        }
    }

    if (!found) {
        cout << search << " is not present in the array." << endl;
    }

    return 0;
    

Output

30 is present at location 3.   

Binary Search

1. Start with a sorted array or list. For binary search to work correctly, the elements must be in ascending or descending order.
2. Set two pointers, low and high, to the beginning and end of the search space, respectively. Initially, low = 0 and high = length of the array - 1.
3. Calculate the middle index using the formula: mid = (low + high) / 2. This will give you the index of the element in the middle of the current search space.
4. Compare the target value with the element at the middle index:
   • If they are equal, the target value has been found. Return the index of the middle element.
   • If the target value is less than the middle element, set high = mid - 1 and go to step 3.
   • If the target value is greater than the middle element, set low = mid + 1 and go to step 3.
5. Repeat steps 3-4 until the target value is found or low > high. If low becomes greater than high, it means the target value is not present in the array.

Pseudocode for Binary Search Algorithm

BinarySearch(array, target): left = 0 // Initialize the left pointer
 right = Length(array) - 1 // Initialize the right pointer while left <= right:
 mid = (left + right) / 2 // Calculate the middle index if array[mid] == target:
 return mid // Target found at the middle index
 else if array[mid] < target:
 left = mid + 1 // Adjust left pointer
 else:
 right = mid - 1 // Adjust right pointer return -1 // Target not found in the array 

Example of Binary Search

size = 6
lst = [1, 3, 5, 4, 10, 7]
sElement = 10

f = 0
l = size - 1
m = (f + l) // 2

while f <= l:
    if lst[m] < sElement:
        f = m + 1
    elif lst[m] == sElement:
        print("Element found at index", m, ".")
        break
    else:
        l = m - 1
    m = (f + l) // 2

if f > l:
    print("Element not found in the list.")
    

class BinarySearch {
    public static void main(String[] args) {
        int size = 6;
        int[] arr = {1, 3, 5, 4, 10, 7};
        int sElement = 10;

        int f = 0;
        int l = size - 1;
        int m = (f + l) / 2;

        while (f <= l) {
            if (arr[m] < sElement) {
                f = m + 1;
            } else if (arr[m] == sElement) {
                System.out.println("Element found at index " + m + ".");
                break;
            } else {
                l = m - 1;
            }
            m = (f + l) / 2;
        }

        if (f > l) {
            System.out.println("Element not found in the list.");
        }
    }
}
    

#include <iostream>
using namespace std;

int main() {
    int size = 6;
    int arr[] = {1, 3, 5, 4, 10, 7};
    int sElement = 10;

    int f = 0;
    int l = size - 1;
    int m = (f + l) / 2;

    while (f <= l) {
        if (arr[m] < sElement) {
            f = m + 1;
        } else if (arr[m] == sElement) {
            cout << "Element found at index " << m << "." << endl;
            break;
        } else {
            l = m - 1;
        }
        m = (f + l) / 2;
    }

    if (f > l) {
        cout << "Element not found in the list." << endl;
    }

    return 0;
}
    

Output

Element found at index 4.   

Summary