binary_search-task.md

Binary Search Task

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/

My Solution with Time Perfomance check

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);

Results

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