🔍 Searching Algorithms in Data Structures

**Searching** is the process of **finding a particular value** in a given set of data. It is one of the **fundamental operations** in computer science and is used in **databases, search engines, AI, and system applications**.

⚡ Why is Searching Important?

• 🚀 **Fast Data Retrieval** - Required for large datasets.
• 📂 **Efficient Data Management** - Used in databases & file systems.
• 🔄 **Optimized Searching** - Reduces execution time.
• 💡 **Essential for AI & Machine Learning** - Used in pattern recognition.

📌 1. Types of Searching Algorithms

Searching algorithms are mainly classified into **two categories**:

🔎 **1.1 Linear Search (Sequential Search) - O(n)**

Linear search checks **each element one by one** until the desired element is found. It is **simple but inefficient** for large datasets.

🛠️ Implementation (C++)

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

✅ Advantages & ❌ Disadvantages

• ✅ Works on **unsorted arrays**.
• ✅ Simple to implement.
• ❌ **Slow for large datasets** (O(n) time complexity).

⚡ **1.2 Binary Search (Efficient Search) - O(log n)**

Binary search works on a **sorted array** and divides the search space in **half** at each step, making it **much faster** than linear search.

🛠️ Implementation (C++)

    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;
            if (arr[mid] < key) left = mid + 1;
            else right = mid - 1;
        }
        return -1; // Element not found
    }
    

✅ Advantages & ❌ Disadvantages

• ✅ **Much faster** than linear search (O(log n)).
• ✅ Ideal for **large datasets**.
• ❌ Works **only on sorted arrays**.

📌 2. Advanced Searching Algorithms

🔄 **2.1 Jump Search (O(√n))**

Jump search divides the array into **blocks** and checks elements at fixed intervals (**√n steps**). If the desired element is found within a block, it performs **linear search** within that block.

🛠️ Implementation (C++)

    int jumpSearch(int arr[], int n, int key) {
        int step = sqrt(n);
        int prev = 0;
        while (arr[min(step, n) - 1] < key) {
            prev = step;
            step += sqrt(n);
            if (prev >= n) return -1;
        }
        while (arr[prev] < key) {
            prev++;
            if (prev == min(step, n)) return -1;
        }
        return (arr[prev] == key) ? prev : -1;
    }
    

✅ Advantages & ❌ Disadvantages

• ✅ **Faster than linear search**, but slightly slower than binary search.
• ✅ Works on **sorted arrays**.
• ❌ Requires **additional calculations** for block sizes.

🔍 **2.2 Interpolation Search (O(log log n))**

Works like binary search but **improves efficiency** when the data is **uniformly distributed** (e.g., employee IDs, sorted names).

🛠️ Implementation (C++)

    int interpolationSearch(int arr[], int n, int key) {
        int low = 0, high = n - 1;
        while (low <= high && key >= arr[low] && key <= arr[high]) {
            int pos = low + ((key - arr[low]) * (high - low)) / (arr[high] - arr[low]);
            if (arr[pos] == key) return pos;
            if (arr[pos] < key) low = pos + 1;
            else high = pos - 1;
        }
        return -1;
    }
    

✅ Advantages & ❌ Disadvantages

• ✅ **Faster than binary search** for uniform data.
• ❌ Performs **poorly on unevenly distributed data**.

📊 Time Complexity Analysis

🌍 Real-World Applications

• 🔎 **Google Search Engine** - Optimized search algorithms.
• 📂 **Databases & File Systems** - Fast lookups in B-Trees.
• 💾 **Operating Systems** - Process scheduling.
• 📡 **AI & Machine Learning** - Pattern recognition.

🔗 Next Topics

• 📊 Sorting Algorithms
• 🔢 Hashing Techniques