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