Skip to main content

Interpolation Search

 Let's begin!


Interpolation search works better than Binary Search for a Sorted and Uniformly Distributed array. Binary Search goes to the middle element to check irrespective of search-key. On the other hand, Interpolation Search may go to different locations according to search-key.

pos = lo + [ (x-arr[lo])*(hi-lo) / (arr[hi]-arr[Lo]) ]

The idea of formula is to return higher value of pos

When element to be searched is closer to arr[hi]. And

Smaller value when closer to arr[lo]

  • pos = lo + [ (x-arr[lo])*(hi-lo) / (arr[hi]-arr[Lo]) ]
  • arr[] ==> Array where elements need to be searched
  • x     ==> Element to be searched
  • lo    ==> Starting index in arr[]
  • hi    ==> Ending index in arr[]

Comments

Post a Comment

Popular posts from this blog

Bubble Sort

 Let's begin! Bubble Sort is a Sorting Algorithm which has two parts: Bubbles up the largest element at the last. Keep checking if the list is sorted. One function will keep bringing the biggest elements at the last of the list and another function will recursively calling it until the list is sorted.
Post a Comment
Read more

Insertion Sort

Let's begin! Insertion sort is a Sorting Algorithm which have average time complexity as polynomial square and best case as linear. It has two function: Function which linearly proceeds through array. Helper Function to compare and swap the element if required within the given range. If the function finds that right element is smaller then left element then it will call the helper function to compare and swap the elements if necessary.
Post a Comment
Read more

Jump Search

 Let's begin! It's a Searching Algorithm with average time complexity as root n. Instead of going one by one through elements (like linear search), it jumps from element to element in a sorted array. The jump value is root of the length of array. If target element is found return true. Else If  current element is less than target and within the range call the function with change parameters. Else If  current element is greater than target and within the range call the function with change parameters. Else return false.
Post a Comment
Read more