fork download
copy 
  1. def interpolation_search(arr, x):
  2.     low = 0
  3.     high = len(arr) - 1
  4.  
  5.     while low <= high and arr[low] <= x <= arr[high]:
  6.         if arr[high] == arr[low]:
  7.             return low if arr[low] == x else -1
  8.  
  9.         pos = low + (x - arr[low]) * (high - low) // (arr[high] - arr[low])
  10.  
  11.         if arr[pos] == x:
  12.             return pos
  13.         elif arr[pos] < x:
  14.             low = pos + 1
  15.         else:
  16.             high = pos - 1
  17.  
  18.     return -1
  19.  
  20. # Example usage:
  21. arr = [10, 20, 30, 40, 50, 60, 70]
  22. x = 50
  23. result = interpolation_search(arr, x)
  24. if result != -1:
  25.     print(f"Found {x} at index: {result}")
  26. else:
  27.     print("Number not found.")
  28. # your code goes here
Success #stdin #stdout 0.08s 14156KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Found 50 at index: 4
https://ideone.com/dnCbjJ
language:
Python 3 (python  3.12)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!