0
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.