Searching in Data Structures - Its Types, Methods & Techniques

Searching in Data Structures - Its Types, Methods & Techniques

09 May 2024
Beginner
10.8K Views
18 min read
Learn via Video Course & by Doing Hands-on Labs

Data Structures & Algorithms Free Course

Searching in Data Structures: An Overview

We all are familiar with the word search. It is to find a particular thing or item from a group of items. It is one of the most commonly used programming concepts in everyday life.

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?

Searching is the fundamental process of locating a specific element or item within a collection of data. This collection of data can be arrays, lists, trees, or other structured representations. Data structures are complex systems designed to organize vast amounts of information. Searching within a data structure is one of the most critical operations performed on stored data.

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

Data structures require specialized search algorithms to enable effective retrieval of a variety of information, from web content to scientific data. Computers would struggle to process large amounts of data effectively without these techniques. Searching Algorithms are designed to check for an element or retrieve an element from any data structure where it is stored. Hence, it is important to understand different search algorithms and why it is important to use one over another.

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
Finding the right data structure can take some effort, but ultimately it will be worth it. Without a data structure, searching for information can become an impossible task and could waste valuable time. With knowledge of using data structures for search algorithms, & searching techniques in the data structure, this task can become easier and more efficient when looking for specific information within large sets of data. For more information, you can check our Data Structures Certification.

FAQs

Q1. What are some of the types of searching techniques in data structures?

Linear search, Binary search, Interpolation Search, Fibonacci Search, Exponential Search, Ternary Search, Jump Search

Q2. Does Binary Search work on unsorted arrays?

No, binary search works only on sorted arrays.

Q3. What is Ternary Search in Data Structures?

Ternary Search is a divide-and-conquer technique that divides the search space into three parts instead of two based on two splitting points.
Share Article

Live Classes Schedule

Our learn-by-building-project method enables you to build practical/coding experience that sticks. 95% of our learners say they have confidence and remember more when they learn by building real world projects.
Full Stack .Net Certification Training May 26 SAT, SUN
Filling Fast
07:00AM to 09:00AM (IST)
Get Details
ASP.NET Core Certification Training May 26 SAT, SUN
Filling Fast
08:30PM to 10:30PM (IST)
Get Details
Advanced Full-Stack .NET Developer Certification Training May 26 SAT, SUN
Filling Fast
08:30PM to 10:30PM (IST)
Get Details
Azure DevOps Certification Training Course Jun 01 SAT, SUN
Filling Fast
10:00AM to 12:00PM (IST)
Get Details
Data Structures and Algorithms Training Jun 04 TUE, FRI
Filling Fast
08:30PM to 10:00PM (IST)
Get Details
ASP.NET Core Certification Training Jun 14 MON, WED, FRI
Filling Fast
07:00AM to 08:30AM (IST)
Get Details
ASP.NET Core (Project) Jun 22 SAT, SUN
Filling Fast
08:30PM to 10:30PM (IST)
Get Details

Can't find convenient schedule? Let us know

About Author
Amit Kumar Ghosh (SDE and Mentor)

A passionate professional with over 6 years of experience in development and training. He is passionate about learning new technologies and sharing his experience with professionals. He is an expert in C/C++, Java, Python and DSA.
Accept cookies & close this