We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
instead of using binary search over the sorted array, using interpolation search would be tardly more efficient:
compute mid at every point using:
mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])
where −
A = list
Lo = Lowest index of the list
Hi = Highest index of the list
A[n] = Value stored at index n in the list
X = element to be searched
Proven that time complexity in this case would be log(log n) per search, so for n elements it would be n(log(log n) , however when it comes to big O, the effective worst case for O(nlogn) + O(n(log(logn))) would still remain O(nlogn).
Let me know if you have some thoughts here
Pairs
You are viewing a single comment's thread. Return to all comments →
instead of using binary search over the sorted array, using interpolation search would be tardly more efficient: compute mid at every point using: mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])
where − A = list Lo = Lowest index of the list Hi = Highest index of the list A[n] = Value stored at index n in the list X = element to be searched Proven that time complexity in this case would be log(log n) per search, so for n elements it would be n(log(log n) , however when it comes to big O, the effective worst case for O(nlogn) + O(n(log(logn))) would still remain O(nlogn). Let me know if you have some thoughts here