Task: We have an array sorted in ascending order:
a = [ 3, 4, 6, 9, 10, 12, 14, 15, 17, 19, 21 ]; Define a function f(a, x) that would return x, the nearest smallest number, or -1 on error.
Example:
f(a, 12) = 12
f(a, 13) = 12
Read article on Russian https://habr.com/ru/companies/ispsystem/articles/779224/
function fBinarySearch(a, x) {
let left = 0;
let right = a.length - 1;
let result = -1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (a[mid] <= x) {
result = a[mid];
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
function fLinearSearch(a, x) {
let result = -1;
for (let i = 0; i < a.length; i++) {
if (a[i] <= x) {
result = a[i];
} else {
break;
}
}
return result;
}
function measurePerformance(a, x, iterations) {
let binarySearchTotalTime = 0;
let linearSearchTotalTime = 0;
for (let i = 0; i < iterations; i++) {
let start = process.uptime();
fBinarySearch(a, x);
let end = process.uptime();
binarySearchTotalTime += end - start;
start = process.uptime();
fLinearSearch(a, x);
end = process.uptime();
linearSearchTotalTime += end - start;
}
let binarySearchAvgTime = binarySearchTotalTime / iterations;
let linearSearchAvgTime = linearSearchTotalTime / iterations;
let percentageDifference =
((linearSearchAvgTime - binarySearchAvgTime) / linearSearchAvgTime) *
100;
console.log(
`fBinarySearch is ${percentageDifference.toFixed(
2
)}% faster than fLinearSearch with ${iterations} iterations`
);
}
let a = [3, 4, 6, 9, 10, 12, 14, 15, 17, 19, 21];
let x = 13;
let iterations = 1000000000;
measurePerformance(a, x, iterations);
For 100 iterations: fBinarySearch is -9.91% faster than fLinearSearch with 100 iterations
For 1 000 iterations: fBinarySearch is 31.52% faster than fLinearSearch with 1000 iterations
For 1 000 000 iterations: fBinarySearch is -16.49% faster than fLinearSearch with 1000000 iterations
For 1 000 000 000 iterations: fBinarySearch is -15.94% faster than fLinearSearch with 1000000000 iterations