|
| 1 | +// import visualization libraries { |
| 2 | +const { Tracer, Array1DTracer, ChartTracer, LogTracer, Randomize, Layout, VerticalLayout } = require('algorithm-visualizer'); |
| 3 | +// } |
| 4 | + |
| 5 | +// define tracer variables { |
| 6 | +const chart = new ChartTracer(); |
| 7 | +const tracer = new Array1DTracer(); |
| 8 | +const logger = new LogTracer(); |
| 9 | +Layout.setRoot(new VerticalLayout([chart, tracer, logger])); |
| 10 | +const D = Randomize.Array1D({ N: 15, value: () => Randomize.Integer({ min: 23, max: 250 }), sorted: true }); |
| 11 | +tracer.set(D); |
| 12 | +tracer.chart(chart); |
| 13 | +Tracer.delay(); |
| 14 | +// } |
| 15 | + |
| 16 | +// define input variables |
| 17 | + |
| 18 | +const element = D[Randomize.Integer({ min: 0, max: D.length - 1 })]; |
| 19 | + |
| 20 | +function interpolationSearch(arr, lo, hi, x){ |
| 21 | + let pos; |
| 22 | + |
| 23 | + // visualize { |
| 24 | + tracer.select(lo); |
| 25 | + tracer.select(hi); |
| 26 | + Tracer.delay(); |
| 27 | + //} |
| 28 | + |
| 29 | + // Since array is sorted, an element present |
| 30 | + // in array must be in range defined by corner |
| 31 | + |
| 32 | + if (lo <= hi && x >= arr[lo] && x <= arr[hi]) { |
| 33 | + |
| 34 | + // Probing the position with keeping |
| 35 | + // uniform distribution in mind. |
| 36 | + pos = lo + Math.floor(((hi - lo) / (arr[hi] - arr[lo])) * (x - arr[lo])); |
| 37 | + |
| 38 | + // visualize { |
| 39 | + tracer.patch(pos); |
| 40 | + Tracer.delay(); |
| 41 | + logger.println(`hi: ${hi}`); |
| 42 | + logger.println(`lo: ${lo}`); |
| 43 | + logger.println(`Searching ${element} at pos: ${pos}`); |
| 44 | + Tracer.delay(); |
| 45 | + |
| 46 | + // } |
| 47 | + |
| 48 | + // Condition of target found |
| 49 | + if (arr[pos] == x){ |
| 50 | + // visualize { |
| 51 | + tracer.deselect(hi); |
| 52 | + tracer.deselect(lo); |
| 53 | + Tracer.delay(); |
| 54 | + logger.println(`${element} found at pos: ${pos}`); |
| 55 | + // } |
| 56 | + return pos; |
| 57 | + } |
| 58 | + |
| 59 | + // If x is larger, x is in right sub array |
| 60 | + if (arr[pos] < x){ |
| 61 | + // visualize { |
| 62 | + tracer.deselect(hi); |
| 63 | + tracer.deselect(lo); |
| 64 | + tracer.depatch(pos); |
| 65 | + Tracer.delay(); |
| 66 | + logger.println(`${element} is smaller than ${arr[pos]}`); |
| 67 | + logger.println(`lo becomes pos+1: ${pos+1}`); |
| 68 | + // } |
| 69 | + return interpolationSearch(arr, pos + 1, hi, x); |
| 70 | + } |
| 71 | + |
| 72 | + // If x is smaller, x is in left sub array |
| 73 | + if (arr[pos] > x){ |
| 74 | + // visualize { |
| 75 | + tracer.deselect(hi); |
| 76 | + tracer.deselect(lo); |
| 77 | + tracer.depatch(pos); |
| 78 | + Tracer.delay(); |
| 79 | + logger.println(`${element} is greater than ${arr[pos]}`); |
| 80 | + logger.println(`hi becomes pos-1: ${pos-1}`); |
| 81 | + // } |
| 82 | + |
| 83 | + return interpolationSearch(arr, lo, pos - 1, x); |
| 84 | + } |
| 85 | + } |
| 86 | + return -1; |
| 87 | +} |
| 88 | + |
| 89 | +interpolationSearch(D,0,D.length-1,element) |
| 90 | + |
0 commit comments