Searching Algorithms

#include <stdio.h>

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

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 30;
    
    int result = linearSearch(arr, n, key);
    if (result != -1)
        printf("Found at index %d\n", result);
    else
        printf("Not found\n");
    
    return 0;
}

#include <stdio.h>

// Iterative
int binarySearch(int arr[], int n, int key) {
    int left = 0, right = n - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == key)
            return mid;
        else if (arr[mid] < key)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

// Recursive
int binarySearchRecursive(int arr[], int left, int right, int key) {
    if (left > right) return -1;
    
    int mid = left + (right - left) / 2;
    
    if (arr[mid] == key)
        return mid;
    else if (arr[mid] < key)
        return binarySearchRecursive(arr, mid + 1, right, key);
    else
        return binarySearchRecursive(arr, left, mid - 1, key);
}

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

#define TABLE_SIZE 10

typedef struct Node {
    int key;
    int value;
    struct Node* next;
} Node;

typedef struct HashTable {
    Node* buckets[TABLE_SIZE];
} HashTable;

// Simple hash function
int hash(int key) {
    return key % TABLE_SIZE;
}

// Create new node
Node* createNode(int key, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->value = value;
    newNode->next = NULL;
    return newNode;
}

// Initialize hash table
void initHashTable(HashTable* ht) {
    for (int i = 0; i < TABLE_SIZE; i++)
        ht->buckets[i] = NULL;
}

// Insert using separate chaining
void insert(HashTable* ht, int key, int value) {
    int index = hash(key);
    Node* newNode = createNode(key, value);
    
    // Insert at head of list
    newNode->next = ht->buckets[index];
    ht->buckets[index] = newNode;
}

// Search
int search(HashTable* ht, int key) {
    int index = hash(key);
    Node* current = ht->buckets[index];
    
    while (current != NULL) {
        if (current->key == key)
            return current->value;
        current = current->next;
    }
    return -1; // Not found
}

// Delete
void delete(HashTable* ht, int key) {
    int index = hash(key);
    Node* current = ht->buckets[index];
    Node* prev = NULL;
    
    while (current != NULL) {
        if (current->key == key) {
            if (prev == NULL)
                ht->buckets[index] = current->next;
            else
                prev->next = current->next;
            free(current);
            return;
        }
        prev = current;
        current = current->next;
    }
}

// Display hash table
void display(HashTable* ht) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        printf("Bucket %d: ", i);
        Node* current = ht->buckets[i];
        while (current != NULL) {
            printf("(%d,%d) → ", current->key, current->value);
            current = current->next;
        }
        printf("NULL\n");
    }
}

int main() {
    HashTable ht;
    initHashTable(&ht);
    
    insert(&ht, 5, 100);
    insert(&ht, 15, 200);  // Collision with 5 (both hash to 5)
    insert(&ht, 25, 300);  // Another collision
    insert(&ht, 7, 400);
    
    printf("Hash Table:\n");
    display(&ht);
    
    printf("\nSearch 15: %d\n", search(&ht, 15));
    printf("Search 100: %d\n", search(&ht, 100));  // Not found
    
    return 0;
}

#include <stdio.h>

int interpolationSearch(int arr[], int n, int key) {
    int low = 0, high = n - 1;
    
    // Key must be in range [low, high] and array must be uniformly distributed
    while (low <= high && key >= arr[low] && key <= arr[high]) {
        
        // If array has only one element
        if (low == high) {
            if (arr[low] == key) return low;
            return -1;
        }
        
        // Probing the position
        // Formula: low + ((key - arr[low]) * (high - low)) / (arr[high] - arr[low])
        int pos = low + ((key - arr[low]) * (high - low)) / (arr[high] - arr[low]);
        
        // Check if key is at pos
        if (arr[pos] == key)
            return pos;
        
        // If key is larger, search right subarray
        if (arr[pos] < key)
            low = pos + 1;
        // If key is smaller, search left subarray
        else
            high = pos - 1;
    }
    
    return -1; // Not found
}

int main() {
    int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 65;
    
    int result = interpolationSearch(arr, n, key);
    
    if (result != -1)
        printf("Element %d found at index %d\n", key, result);
    else
        printf("Element %d not found\n", key);
    
    return 0;
}

#include <stdio.h>
#include <math.h>

int jumpSearch(int arr[], int n, int key) {
    // Find optimal block size to jump
    int step = sqrt(n);
    int prev = 0;
    
    // Jump until we find a block where key could be
    while (arr[min(step, n) - 1] < key) {
        prev = step;
        step += sqrt(n);
        
        // If we've gone past the array, key not present
        if (prev >= n)
            return -1;
    }
    
    // Linear search within the identified block
    while (arr[prev] < key) {
        prev++;
        
        // If we reach next block, key not present
        if (prev == min(step, n))
            return -1;
    }
    
    // Check if element found
    if (arr[prev] == key)
        return prev;
    
    return -1;
}

// Helper function
int min(int a, int b) {
    return (a < b) ? a : b;
}

int main() {
    int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 13;
    
    int result = jumpSearch(arr, n, key);
    
    if (result != -1)
        printf("Element %d found at index %d\n", key, result);
    else
        printf("Element not found\n");
    
    return 0;
}

#include <stdio.h>

#define INDEX_SIZE 5  // Number of index entries
#define BLOCK_SIZE 10 // Elements per block

typedef struct {
    int key;      // Maximum key in this block
    int position; // Starting position in main array
} IndexEntry;

// Create index table
void createIndex(int arr[], int n, IndexEntry index[]) {
    for (int i = 0; i < INDEX_SIZE && i * BLOCK_SIZE < n; i++) {
        index[i].position = i * BLOCK_SIZE;
        // Store max key in block (last element)
        int end = (i + 1) * BLOCK_SIZE - 1;
        if (end >= n) end = n - 1;
        index[i].key = arr[end];
    }
}

int indexSequentialSearch(int arr[], int n, IndexEntry index[], int key) {
    // Search index table to find correct block
    int block = -1;
    for (int i = 0; i < INDEX_SIZE; i++) {
        if (key <= index[i].key) {
            block = i;
            break;
        }
    }
    
    // If block not found in index
    if (block == -1)
        return -1;
    
    // Calculate search range in main array
    int start = index[block].position;
    int end = start + BLOCK_SIZE;
    if (end > n) end = n;
    
    // Sequential search within block
    for (int i = start; i < end; i++) {
        if (arr[i] == key)
            return i;
        if (arr[i] > key)
            return -1; // Early exit (array is sorted)
    }
    
    return -1;
}

int main() {
    int arr[] = {3, 6, 9, 12, 15, 18, 21, 24, 27, 30,  
                 33, 36, 39, 42, 45, 48, 51, 54, 57, 60};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    IndexEntry index[INDEX_SIZE];
    createIndex(arr, n, index);
    
    printf("Index Table:\n");
    for (int i = 0; i < INDEX_SIZE; i++) {
        printf("Entry %d: key=%d, position=%d\n", 
               i, index[i].key, index[i].position);
    }
    
    int key = 33;
    int result = indexSequentialSearch(arr, n, index, key);
    
    if (result != -1)
        printf("\nElement %d found at index %d\n", key, result);
    else
        printf("\nElement not found\n");
    
    return 0;
}