FilesExpand file tree

 master

/

interpolationSearch.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

53 lines (44 loc) · 1.19 KB

 master

/

interpolationSearch.java

Copy path

Top

File metadata and controls

• Code
• Blame

53 lines (44 loc) · 1.19 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

52

class Test

{

// Array of items on which search will

// be conducted.

static int arr[] = new int[]{10, 12, 13, 16, 18, 19, 20, 21, 22, 23,

24, 33, 35, 42, 47};

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

// index of it, else returns -1.

static int interpolationSearch(int x)

{

// Find indexes of two corners

int lo = 0, hi = (arr.length - 1);

// Since array is sorted, an element present

// in array must be in range defined by corner

while (lo <= hi && x >= arr[lo] && x <= arr[hi])

{

// Probing the position with keeping

// uniform distribution in mind.

int pos = lo + (((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 method

public static void main(String[] args)

{

int x = 18; // Element to be searched

int index = interpolationSearch(x);

// If element was found

if (index != -1)

System.out.println("Element found at index " + index);

else

System.out.println("Element not found.");

}

}