fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	public static int interpolationSearch(int[] sortedArray, int toFind)
  11. 	    {
  12. 	        int low = 0;
  13. 	        int high = sortedArray.length - 1;
  14. 	        int mid;
  15. 	        while (sortedArray[low] <= toFind && sortedArray[high] >= toFind) 
  16. 	        {
  17. 	            if (sortedArray[high] - sortedArray[low] == 0)
  18. 	                return (low + high)/2;
  19. 	            /** out of range is possible  here **/
  20. 	             mid = low + ((toFind - sortedArray[low]) * (high - low)) / (sortedArray[high] - sortedArray[low]);  
  21.  
  22. 	             if (sortedArray[mid] < toFind)
  23. 	                 low = mid + 1;
  24. 	             else if (sortedArray[mid] > toFind)
  25. 	                 high = mid - 1;
  26. 	             else
  27. 	                 return mid;
  28. 	        }
  29. 	        if (sortedArray[low] == toFind)
  30. 	            return low;
  31. 	           /** not found **/
  32. 	        else
  33. 	            return -1; 
  34. 	    }    
  35. 	    /** Main method **/
  36. 	    public static void main(String[] args) 
  37. 	    {
  38. 	        Scanner scan = new Scanner( System.in );        
  39. 	        System.out.println("Interpolation Search Test\n");
  40. 	        int n, i;
  41.  
  42. 	        /** Accept number of elements **/
  43.  
  44. 	        System.out.println("Enter number of integer elements");
  45. 	        n = scan.nextInt();
  46.  
  47. 	        /** Create integer array on n elements **/
  48. 	        int arr[] = new int[ n ];
  49. 	        /** Accept elements **/
  50. 	        System.out.println("\nEnter "+ n +" sorted integer elements");
  51. 	        for (i = 0; i < n; i++)
  52. 	            arr[i] = scan.nextInt();
  53. 	        System.out.println("\nEnter element to search for : ");
  54. 	        int key = scan.nextInt();
  55.  
  56. 	        int result = interpolationSearch(arr, key);
  57.  
  58. 	        if (result == -1)
  59. 	            System.out.println("\n"+ key +" element not found");
  60. 	        else
  61. 	            System.out.println("\n"+ key +" elemnt found at position "+ result);
  62.  
  63. 	    }
  64. }
Success #stdin #stdout 0.14s 321088KB
comments (?)
stdin
copy 
5
1 2 3 4 5
2
stdout
copy 
Interpolation Search Test

Enter number of integer elements

Enter 5 sorted integer elements

Enter element to search for : 

2 elemnt found at position 1
https://ideone.com/4pxceg
language:
Java (HotSpot 12)
created:
8 years 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!