GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — Algorithm/java/coding/binarySearch_Interpolation.java at master · lelea2/Algorithm Expand file tree/ Copy pathbinarySearch_Interpolation.javaMore file actions 36 lines (33 loc) · 1.74 KB / Copy pathbinarySearch_Interpolation.javaFile metadata and controls36 lines (33 loc) · 1.74 KB 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 /** * Interpolation search better than binary search * Referenced from: https://blog.imaginea.com/interpolation-search-a-search-algorithm-better-than-binary-search/ */ // The difference between the binary and the interpolation sort is that the binary search always splits the the array in half and inspects the middle element. // Interpolation search calculates a position p, where the value should be placed in accordance to the distribution of values a splits the array at p. // If the array contains numbers 0, 1, 2, ..., 10 and we are looking for 9 the binary search needs three steps – split at 5, split at 8, split at 9 (found). // The interpolation search calculates the probable position (index 9) and immediately finds the value. // Run time: **O(log(logn))** /** * Interpolation search * @param array array with uniformly distributed values in ascending order * @param value searched value * @param from first index that might be touched * @param to last index that might be touched * @return index index of the searched value in the array, -1 if not found */ public static int interpolationSearch(int[] array, int value, int from, int to) { if(array[from] == value) { return from; } else if(from == to || array[from] == array[to]) { return -1; //not found } //probable position of the searched value int index = from + ((to - from)/(array[to] - array[from])) * (value - array[from]); if(array[index] == value) { return index;//found } else if(array[index] < value) { //continue in the right part of the array return interpolationSearch(array, value, index + 1, to); } else { //continue in the left part of the array return interpolationSearch(array, value, from, index - 1); } } |
| You are visitor 01402503 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |