Sequential Search & Index Sequential Search

1️⃣ Sequential Search (Linear Search)

🔹 Simple searching technique that checks elements one by one.
🔹 Works on unsorted or sorted data.
🔹 Time Complexity:

• Best Case: O(1) (Element found at the first position).
• Worst Case: O(n) (Element at the last position or not present).
  🔹 Used when:
• Data is small.
• No sorting is required.
• Searching once or rarely (no need for optimizations).

✅ C Program: Sequential Search

#include <stdio.h>

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

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

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

    return 0;
}

✅ Works on unsorted data
❌ Slow for large datasets

---

2️⃣ Index Sequential Search

🔹 Optimized form of Sequential Search.
🔹 Used when data is large and sorted.
🔹 Divides data into blocks, creating an index table for quick lookups.
🔹 Steps:

1. Create an index table containing references to certain elements in the data.
2. Search in the index table to locate the approximate block.
3. Perform Sequential Search in that block.
   🔹 Time Complexity:

• Best Case: O(1) (if found in index).
• Worst Case: O(√n) (if searched element is at the end).

---

✅ C Program: Index Sequential Search

#include <stdio.h>

#define SIZE 10
#define INDEX_SIZE 3  // Number of index entries

// Structure to store index
struct IndexTable {
    int key;
    int position;
};

// Function to perform index sequential search
int indexSequentialSearch(int arr[], struct IndexTable index[], int key) {
    int i, start, end;
    
    // Step 1: Find the index block
    for (i = 0; i < INDEX_SIZE; i++) {
        if (index[i].key >= key) break;
    }

    // Define the search range
    if (i == 0) start = 0;
    else start = index[i - 1].position;
    
    end = index[i].position;

    // Step 2: Perform sequential search in the found block
    for (int j = start; j < end; j++) {
        if (arr[j] == key) return j;
    }
    
    return -1;  // Element not found
}

int main() {
    int arr[SIZE] = {1, 3, 5, 7, 9, 12, 15, 18, 21, 25};

    // Creating an index table
    struct IndexTable index[INDEX_SIZE] = {
        {5, 2},  // First block starts at index 0
        {12, 5}, // Second block starts at index 2
        {21, 8}  // Third block starts at index 5
    };

    int key = 12;

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

    return 0;
}

✅ Faster than Sequential Search
✅ Efficient for large datasets
❌ Needs sorted data and index table

---

3️⃣ Comparison: Sequential vs. Index Sequential Search

Feature	Sequential Search	Index Sequential Search
Data Requirement	Works on unsorted & sorted data	Works only on sorted data
Time Complexity (Worst Case)	O(n)	O(√n)
Best for	Small datasets	Large datasets
Memory Usage	No extra memory required	Extra memory for index table
Performance	Slower for large data	Faster due to indexing