Searching in Data Structures - Its Types, Methods & Techniques

Searching in Data Structures - Its Types, Methods & Techniques

06 Jun 2024
Beginner
22K Views
18 min read
Learn with an interactive course and practical hands-on labs

Data Structures & Algorithms Free Course with Certificate

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

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

No, binary search works only on sorted arrays.

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.
ASP.NET Core Certification Training Nov 08 MON, TUE, WED, THU, FRI
Filling Fast
07:00AM to 08:30AM (IST)
Get Details
Azure Developer Certification Training Nov 09 SAT, SUN
Filling Fast
08:30PM to 10:30PM (IST)
Get Details
.NET Solution Architect Certification Training Nov 09 SAT, SUN
Filling Fast
05:30PM to 07:30PM (IST)
Get Details
.NET Microservices Certification Training Nov 09 SAT, SUN
Filling Fast
05:30PM to 07:30PM (IST)
Get Details
Microsoft Azure Cloud Architect with AI Nov 10 SAT, SUN
Filling Fast
07:00AM to 09:00AM (IST)
Get Details
ASP.NET Core Certification Training Nov 10 SAT, SUN
Filling Fast
10:00AM to 12:00PM (IST)
Get Details
Angular Certification Training Nov 17 SAT, SUN
Filling Fast
06:00PM to 08:00PM (IST)
Get Details
Software Architecture and Design Training Nov 24 SAT, SUN
Filling Fast
10:00AM to 12:00PM (IST)
Get Details
.NET Solution Architect Certification Training Nov 24 SAT, SUN
Filling Fast
10:00AM to 12:00PM (IST)
Get Details

Can't find convenient schedule? Let us know

About Author
Amit Kumar Ghosh (SDE and Mentor at Scholarhat)

As a software developer with a wealth of experience, he brings a unique combination of technical acumen and a passion for mentorship to my role. With 6 years of experience, he has honed the skills in C/C++, Java, Python, SQL, C#, JavaScript, React, Java Spring etc. and has a proven track record of delivering high-quality, scalable software solutions and core Computer fundamental knowledge DSA, OOPs, CN, OS etc.

As a teacher, his approach revolves around interactive techniques, prioritizing hands-on learning and real-world projects. He explains concepts clearly, offer practical examples, and encourage questions to foster a supportive environment.
Accept cookies & close this