Data Structure & Algorithm: Interpolation Search

    Interpolation search is a searching algorithm that applies to a sorted & equally distributed array, and it is an improved variant of binary search . Like binary search, it uses the divide and conquer algorithm but does not divide the array into two equal parts to search the element. As compared to a linear search, binary search is more efficient, but the interpolation search is more effective than any other searching algorithm.

    With binary searching, if we want to locate the position of an element in the array, we require O(log n) time complexity, but we have another searching algorithm that is capable of searching an element with O(log log n) time complexity.

    As binary search always checks for the middle index, rather than considering the element, the interpolation search considers the searched element and, based on an algorithm, checks for those locations for which the value of the element is being searched.

    Time Complexity

    Linear Search Binary Search Interpolation Search
    O(n) O(log n) O(log log n)

    Algorithm

    • The array must be sorted
    • Make a start =0 and end = n-1
    • Use a formula to locate the position, which brings us near to the searched element
    pos = start + (((end-start)/(arr[end]-arr[start])) * (target-arr[start]))
    • If arr[pos] == target return the pos
    • If target > arr[pos] start = pos+1
    • Else end = pos-1

    Pseudocode

    start =0
    end = len(arr) -1
    found = false
    while found == false and start <=end
    {            
       pos = start + (((end-start)/(arr[end]-arr[start])) * (target-arr[start]))       
       if arr[pos]==target
          {
             return pos
          }
       if target > arr[pos]
          {
              start = pos+1
          }
       else
          {
           end = pos-1
          }
    }

    Implementation

    Python:

    def Interpolation_Search (arr,target):
        start = 0
        end = len(arr)-1
        found = False
    
        while start <= end and found == False:
            if start == end:
                if arr[start] == target: 
                    return "{} is at {} index".format(target,pos)
                return "not found"    
    
            pos = start + (((end-start)//(arr[end]-arr[start])) * (target-arr[start]))               
    
            if arr[pos] == target:      
                return "{} is at {} index".format(target,pos)  
    
            if arr[pos] < target:
                start = pos + 1;
            else:
                end = pos - 1;    
    
        return "Not Found"
    
    arr = [10, 20, 40, 77, 86, 89, 91]
    print(Interpolation_Search(arr, 86))

    Output:

    86 is at 4 index

    Conclusion

    With this, we are concluding our tutorial on interpolation search. This search is highly helpful in applications in various real-life scenarios where efficient data retrieval is crucial, like weather forecasting, database systems, library catalogs, and more. Overall, interpolation search plays a vital role in locating specific data points within vast datasets rapidly.

    We hope that this information proves helpful to you. In case of any queries, please let us know in the comment section below.

    Good luck!

    People are also reading: