FilesExpand file tree

 master

/

Interpolation.py

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

51 lines (40 loc) · 1.17 KB

 master

/

Interpolation.py

Top

File metadata and controls

• Code
• Blame

51 lines (40 loc) · 1.17 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

# Python program to implement interpolation search

# If x is present in arr[0..n-1], then returns

# index of it, else returns -1

def interpolationSearch(arr, n, x):

# Find indexs of two corners

lo = 0

hi = (n - 1)

# Since array is sorted, an element present

# in array must be in range defined by corner

while lo <= hi and x >= arr[lo] and x <= arr[hi]:

if lo == hi:

if arr[lo] == x:

return lo;

return -1;

# Probing the position with keeping

# uniform distribution in mind.

pos = lo + int(((float(hi - lo) /

( arr[hi] - arr[lo])) * ( x - arr[lo])))

# Condition of target found

if arr[pos] == x:

return pos

# If x is larger, x is in upper part

if arr[pos] < x:

lo = pos + 1;

# If x is smaller, x is in lower part

else:

hi = pos - 1;

return -1

# Driver Code

# Array of items oin which search will be conducted

arr = [10, 12, 13, 16, 18, 19, 20, 21, \

22, 23, 24, 33, 35, 42, 47]

n = len(arr)

x = 18 # Element to be searched

index = interpolationSearch(arr, n, x)

if index != -1:

print "Element found at index",index

else:

print "Element not found"

# This code is contributed by Harshit Agrawal