Chapter 15 – Searching Algorithms

Chapter 15: Searching Algorithms

Introduction

Searching and sorting algorithms are crucial in Data Structures and Algorithms (DSA) because they help us organize and access data efficiently. Whether you’re building a search engine, a database, or even a simple contact list, you’ll need to understand these algorithms deeply. This chapter focuses on two important tasks:

1. Searching: Finding a specific element within a dataset.
2. Sorting: Arranging data in a certain order (ascending, descending, etc.) for better management.

To keep things interesting, we’ll break the chapter into digestible sections. First, we’ll focus on searching algorithms, and then in subsequent parts, we’ll cover sorting algorithms. As we proceed, remember to try the code examples on your IDE or notebook—this practice will cement your understanding.

---

Part 1: Searching Algorithms

---

1.1 Linear Search

Let’s start with one of the simplest searching algorithms: Linear Search. Though not the most efficient for large datasets, linear search is straightforward and can be used on unsorted data.

---

Definition:

Linear search traverses the entire data structure from the beginning to the end, comparing each element with the target value. If the target is found, the algorithm returns its position; otherwise, it returns a "not found" result.

---

Use Case:

• Imagine you have a list of unsorted contact names. If you’re looking for someone, linear search is the only choice unless the list is sorted.
• Linear search is often used in small datasets where performance isn’t a concern.

---

Algorithm:

Here’s a simple breakdown of how linear search works:

1. Start at the first element of the data structure.
2. Compare the current element with the target value.
3. If they match, return the index (position).
4. If not, move to the next element.
5. Repeat this process until you find the target or reach the end.

---

Time Complexity:

O(n) — because in the worst case, you might have to check every element.

Let’s implement this in C and C++!

---

C Programming: Linear Search in an Array

#include <stdio.h>

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;  // Target found, return the index
        }
    }
    return -1;  // Target not found
}

int main() {
    int arr[] = {10, 23, 45, 70, 11, 15};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 70;

    int result = linearSearch(arr, n, target);
    if (result != -1) {
        printf("Element found at index: %d\n", result);
    } else {
        printf("Element not found.\n");
    }
    
    return 0;
}

---

C++ Programming: Linear Search in an Array

#include <iostream>
using namespace std;

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;  // Target found, return the index
        }
    }
    return -1;  // Target not found
}

int main() {
    int arr[] = {2, 4, 0, 1, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 1;

    int result = linearSearch(arr, n, target);
    if (result != -1) {
        cout << "Element found at index: " << result << endl;
    } else {
        cout << "Element not found." << endl;
    }
    
    return 0;
}

Explanation:

• In both programs, we create an array of integers and then implement the linear search function.
• The function traverses through the array, comparing each element with the target.
• If it finds the target, it returns the index of the element.
• If not, it returns -1, indicating that the element was not found.

---

Discussion on Linked Lists:

Linear search works similarly in Linked Lists, but instead of indexing like we do in arrays, we traverse the nodes. Since a linked list is a sequential structure without random access, we need to move from node to node.

---

C Programming: Linear Search in a Singly Linked List

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

int linearSearch(struct Node* head, int target) {
    struct Node* current = head;
    int index = 0;

    while (current != NULL) {
        if (current->data == target) {
            return index;
        }
        current = current->next;
        index++;
    }
    
    return -1;  // Target not found
}

// Helper function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

int main() {
    struct Node* head = createNode(10);
    head->next = createNode(20);
    head->next->next = createNode(30);
    head->next->next->next = createNode(40);

    int target = 30;
    int result = linearSearch(head, target);
    
    if (result != -1) {
        printf("Element found at position: %d\n", result);
    } else {
        printf("Element not found.\n");
    }

    return 0;
}

---

Explanation:

• Here, we create a singly linked list and use a linear search algorithm to find the target value.
• We traverse the list node by node, checking each node’s data.
• Since there’s no concept of index in a linked list, we maintain a manual counter (index).
• If we find the target, we return its position. Otherwise, we return -1.

---

Advantages and Disadvantages of Linear Search:

• Advantages:
  • Simple and easy to implement.
  • Works on both sorted and unsorted datasets.
• Disadvantages:
  • Inefficient for large datasets, especially when compared to more advanced algorithms like binary search.
  • Takes linear time in the worst case (O(n)).

---

Where to Use Linear Search:

• When dealing with small datasets or unsorted data.
• For data structures like linked lists, where other search algorithms might be less efficient due to lack of direct indexing.

This concludes our detailed discussion of Linear Search across different data structures.

---

Next Part Preview: Binary Search

In the next part of the chapter, we will dive into the more efficient Binary Search, where we optimize the searching process by dividing the dataset in half. But remember, binary search only works on sorted datasets, so sorting comes into play!

You’ll also see how binary search works not just with arrays but with Binary Search Trees (BSTs), a crucial data structure in DSA.

And as always, feel free to check out resources on digilearn.cloud from Emancipation Edutech Private Limited, where this book is available for free reading!

---

Part 2: Binary Search

---

1.2 Binary Search

Binary Search is a much faster searching algorithm compared to linear search, but it requires the data to be sorted. Instead of checking each element, binary search eliminates half of the dataset with each comparison.

---

Definition:

Binary search repeatedly divides the dataset in half, narrowing down the search to the side where the target might exist. This reduces the number of comparisons significantly.

---

Algorithm:

1. Start with the middle element of the sorted dataset.
2. Compare the target with the middle element:
   • If they match, the search is complete.
   • If the target is smaller, focus on the left half.
   • If the target is larger, focus on the right half.
3. Repeat the process on the remaining half until the target is found or the list is exhausted.

---

Time Complexity:

O(log n) — as each step reduces the search space by half.

---

Binary Search Implementation in C:

#include <stdio.h>

int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            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 target = 10;
    
    int result = binarySearch(arr, 0, n - 1, target);
    
    if (result != -1) {
        printf("Element found at index: %d\n", result);
    } else {
        printf("Element not found.\n");
    }
    
    return 0;
}

Explanation:

• This program works on sorted arrays, recursively dividing the array to find the target element.

---

Advantages and Disadvantages of Binary Search:

• Advantages:

  • Much faster than linear search for sorted datasets.
  • Efficiency increases with larger datasets.

• Disadvantages:

  • Only works on sorted data.
  • Must handle edge cases carefully (especially in linked lists).

---

Binary search is vital for operations in Binary Search Trees (BSTs), which we’ll explore later. For now, keep practicing with different arrays and values.

In the next part, we’ll dive into Sorting Algorithms, starting with the Bubble Sort.

---

Let me know when you’re ready for the sorting algorithms! And don’t forget to check out more resources at digilearn.cloud, provided by Emancipation Edutech Private Limited.