I am reading Algorithms 4ed by Sedgewick and Wayne. I came across this algorithm design question that asks the following:
Write a program that given an array of N integers, finds a closest pair: two values whose difference is no greater than the difference of any other pair (in absolute value). The running time of the program should be linearithmic in the worst case.
I wrote an implementation of this algorithm in javascript and ran a few tests. So far, it looks like the algorithm is correct and also linearithmic. But, I am not very good at proving correctness of algorithms or, in analyzing their time complexity (ammortized). If anyone can help me answer the following it would be great:
- Is the algorithm (added later) correct?
- Is the amortized time complexity linearithmic (i.e., N*lgN)?
The algorithm is given below:
function binarySearch(key, start, arr) { let a = arr[start-1]; // start >= 1 let b = arr[start]; let lo = start+1; let hi = arr.length-1; let getMid = () => Math.floor((lo+hi)/2); let getDiff = (a, b) => Math.abs(a-b); let mid; let diff; let ldiff = getDiff(a, b); let hidx = start; while(lo < hi) { mid = getMid(); diff = getDiff(a, arr[mid]); if(diff < ldiff) { ldiff = diff; hidx = mid; hi = mid-1; } else { lo = mid+1; } } return { highIndex: hidx, leastDiff: ldiff }; } function closestPair(arr) { // returns the nearest, closest pair let ldiff = null; let hidx; let lidx; for(let i=0; i<arr.length-1; ++i) { let { highIndex, leastDiff } = binarySearch(ldiff, i+1, arr); console.log(`hi=$ {highIndex} low=$ {i} ld=$ {leastDiff}`); if(ldiff === null || leastDiff < ldiff) { ldiff = leastDiff; hidx = highIndex; lidx = i; } } if(ldiff !== null && lidx !== null && hidx !== null) { return { leastDiff: ldiff, lowIndex: lidx, highIndex: hidx }; } else null; } To test the algorithm, I had the following tests setup:
if(!module.parent) { let arrs = [ [1, 7, 13, 5, 19, 27, 20, 39, 40], // 2; 19-20/39-40 [3, 2, 10, 6, 9, 5], [-2, 9, 5, 25, 13, -10, -25] ]; for(let arr of arrs) { let s = arr.sort(ascComparator); console.log(`sorted arr: $ {s.toString()}`); let cp = closestPair(s); console.log(cp); } } The output on the console for running the tests were as follows:
sorted arr: 1,5,7,13,19,20,27,39,40 hi=1 low=0 ld=4 hi=2 low=1 ld=2 hi=3 low=2 ld=6 hi=4 low=3 ld=6 hi=5 low=4 ld=1 hi=6 low=5 ld=7 hi=7 low=6 ld=12 hi=8 low=7 ld=1 { leastDiff: 1, lowIndex: 4, highIndex: 5 } sorted arr: 2,3,5,6,9,10 hi=1 low=0 ld=1 hi=2 low=1 ld=2 hi=3 low=2 ld=1 hi=4 low=3 ld=3 hi=5 low=4 ld=1 { leastDiff: 1, lowIndex: 0, highIndex: 1 } sorted arr: -25,-10,-2,5,9,13,25 hi=1 low=0 ld=15 hi=2 low=1 ld=8 hi=3 low=2 ld=7 hi=4 low=3 ld=4 hi=5 low=4 ld=4 hi=6 low=5 ld=12 { leastDiff: 4, lowIndex: 3, highIndex: 4 } 