#95 Max-MinWeights

[magicsung]

Given n > 1 items and a two-pan balance scale with no weights, determine the lightest and the heaviest items in ⌈3n/2⌉ − 2 weighings.

[magicsung]

'use strict'

var n = 100;
var counter = 0;
var items = [];
var max = null;
var min = null;

for (var i = 0; i < n; i++) {
    let rand = Math.round(Math.random() * n * 2);
    items.push(rand)
}

console.log('n = ' + n);
console.log('items =', items);
console.log('max/min:', findMax(items));
console.log('counter =', counter + '/' + (n * 3 / 2 - 2) );

function findMax(arr) {
	// 先取前兩顆並秤重，作為初始基準
    let maxMin = [arr[0], arr[1]];
    if (weighing(maxMin[0], maxMin[1]) === 'less')
        maxMin = [maxMin[1], maxMin[0]];

	// 每次取兩顆並秤重後，重的跟原本重的再秤一次，留下重的；輕的跟輕的再秤一次，留下輕的。
    for (var i = 2; i < arr.length; i += 2) {
        let compare = [arr[i], arr[i+1]];

        if (compare[1] === undefined) {
            compare = [arr[i], arr[i]];
        } else if (weighing(arr[i], arr[i+1]) === 'less') {
            compare = [arr[i+1], arr[i]];
        }

        if (weighing(compare[0], maxMin[0]) === 'greater')
            maxMin[0] = compare[0];

        if (weighing(compare[1], maxMin[1]) === 'less')
            maxMin[1] = compare[1];
    }
    return maxMin;
}

// 秤重
function weighing(a, b) {
    counter++;
    if (a > b) {
        return 'greater';
    } else if (a < b) {
        return 'less';
    } else {
        return 'equal';
    }
}