**Interpolation Search.**Youtube. GFS.**The search works well for uniformly distributed numbers.**

Formula Calculation –So the formula to estimate the position =

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[]

To implement this code, we proceed just like binary search. Instead of mid we use this pos and increase/decrease it accordingly.

Time complexity = O (log log n))

- Recursively implement a linear search.

- Exponential Search. Jump search does a linear search after finding range while exponential search does binary search after finding range. It involves two steps:
- Find range where element is present

Here we increase step in size of 2, ie we keep doubling the step size. In Jump search we increase step in size of**√n..** - Do Binary Search in above found range.

Once we find an index i (after repeated doubling of i), we know that the element must be present between i/2 and i. now do a binary search in i and i/2

`while`

`(i < n && arr[i] <= x)`

`i = i*2;`

- Find range where element is present
- Given a sorted array with possible duplicate elements. Find number of occurrences of input ‘key’ in
*log N*time.

- *** Suppose you have a sorted array of infinite numbers, how would you search an element in the array?

We find the range to search using exponential search. The apply binary search.

**Jump Search**is a searching algorithm for**sorted arrays**. The basic idea is to check fewer elements (than linear search) by jumping ahead by fixed steps or skipping some elements in place of searching all elements. GFG.

We need to find the range in which the number lies. So we check if the number lies in step, the size of step being**√n.**Check the code as it’s pretty clear and simple.

– Works only sorted arrays.

– The optimal size of a block to be jumped is O(√ n). This makes the time complexity of Jump Search O(√ n).

– The time complexity of Jump Search is between Linear Search ( ( O(n) ) and Binary Search ( O (Log n) ).

– Jump search does a linear search after finding range while exponential search does binary search after finding range.

Advertisements