# Linearithmic solution to finding closest pairs in an array of N elements

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:

1. Is the algorithm (added later) correct?
2. 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 }

• This is better suited for codereview.stackexchange.com. – orlp Jul 29 at 20:03
• It’s better if you describe your algorithm more succinctly, in pseudocode or in words. – Yuval Filmus Jul 29 at 20:11
• You can solve this by sorting the array and looking at adjacent elements. – Yuval Filmus Jul 29 at 20:12
• @orlp thanks for pointing that out; I'll add it on codereview – Abrar Hossain Jul 29 at 20:29
• Sorting takes linearithmic time. – Yuval Filmus Jul 29 at 20:32