Tutorial 34

 ------Interpoliation Search

-----By Using Array

#include <iostream>

int interpolationSearch(const int arr[], int low, int high, int key) 

{

  // Check if key is outside array range

  if (key < arr[low] || key > arr[high])

   {

    return -1;

  }

  // Linear search if array is very small

  if (high - low <= 1)

   {

    if (arr[low] == key) {

      return low;

    } else if (arr[high] == key) {

      return high;

    } else {

      return -1;

    }

  }

  // Calculate interpolation position

  int pos = low + (((key - arr[low]) * 

            (high - low)) / (arr[high] - arr[low]));

  // If key is found

  if (arr[pos] == key) 

  {

    return pos;

  }

  // If key is less, search in left half

  if (arr[pos] > key) 

  {

    return interpolationSearch(arr, low, pos - 1, key);

  } 

  else 

  {

    // If key is greater, search in right half

    return interpolationSearch(arr, pos + 1, high, key);

  }

}

int main() {

  int arr[] = {1, 3, 5, 8, 11, 13, 17, 19, 23, 29, 31};

  int n = sizeof(arr) / sizeof(arr[0]);

  int key = 17;

  int index = interpolationSearch(arr, 0, n - 1, key);

  if (index != -1) {

    std::cout << "Element found at index " << index << std::endl;

  } else {

    std::cout << "Element not found" << std::endl;

  }

  return 0;

}

---- By Using Linked List

#include <iostream>

struct Node {

  int data;

  Node* next;

};

int searchLinkedList(Node* head, int key) {

  Node* current = head;

  int position = 0;

  while (current != nullptr) {

    if (current->data == key) {

      return position;

    }

    current = current->next;

    position++;

  }

  return -1; // Key not found

}

int main() {

  // Create a sample linked list

  Node* head = new Node{1, new Node{3, new Node{5, nullptr}}};

  int key = 3;

  int index = searchLinkedList(head, key);

  if (index != -1) {

    std::cout << "Element found at index " << index << std::endl;

  } else {

    std::cout << "Element not found" << std::endl;

  }

  return 0;

}