# 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 } ``