Concept of Searching in Data Structures

 

What is Searching?

Searching is the process of finding a specific element in a collection of data. It is one of the fundamental operations in computer science and plays a crucial role in various applications such as databases, operating systems, and information retrieval.

🔹 Types of Searching Techniques

Searching techniques are broadly classified into two categories: 1️⃣ Linear Search (Sequential Search)
2️⃣ Binary Search (Efficient search for sorted data)

---

1️⃣ Linear Search

🔹 Simple but inefficient method.
🔹 Searches for an element sequentially from the beginning to the end.
🔹 Time Complexity: O(n) (Worst-case scenario: search the entire list).
🔹 Best for small or unsorted data.

✅ C Program: Linear Search

#include <stdio.h>

// Function to perform linear search
int linearSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) return i;  // Element found at index i
    }
    return -1;  // Element not found
}

int main() {
    int arr[] = {5, 3, 8, 4, 2, 9, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 4;

    int index = linearSearch(arr, n, key);
    if (index != -1)
        printf("Element found at index %d\n", index);
    else
        printf("Element not found\n");

    return 0;
}

✅ Simple to implement
❌ Slow for large datasets

---

2️⃣ Binary Search (For Sorted Data)

🔹 Faster and more efficient than linear search.
🔹 Works only on sorted data by dividing the search space in half.
🔹 Time Complexity: O(log n) (Each step reduces the problem size by half).
🔹 Best for large datasets with sorted data.

✅ C Program: Binary Search

#include <stdio.h>

// Function to perform binary search
int binarySearch(int arr[], int left, int right, int key) {
    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == key) return mid;  // Element found

        if (arr[mid] < key) left = mid + 1;  // Search right half
        else right = mid - 1;  // Search left half
    }
    return -1;  // Element not found
}

int main() {
    int arr[] = {2, 4, 5, 7, 8, 9, 12};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 7;

    int index = binarySearch(arr, 0, n - 1, key);
    if (index != -1)
        printf("Element found at index %d\n", index);
    else
        printf("Element not found\n");

    return 0;
}

✅ Much faster than linear search
❌ Requires sorted data

---

3️⃣ Comparison: Linear vs Binary Search

Feature	Linear Search	Binary Search
Data Requirement	Works on unsorted data	Requires sorted data
Time Complexity	O(n)	O(log n)
Performance on Large Data	Slow	Fast
Best Case Complexity	O(1) (if first element is found)	O(1) (if middle element is found)
Worst Case Complexity	O(n)	O(log n)
Use Case	Small datasets, unsorted data	Large datasets, sorted data