binary-search-test

Benchmark created on


Setup

function randomArr(len){
	const arr = [];
	for(let k=0; k<len; k++){
		arr.push(Math.random()*10);
	};
	return arr;
};

const input = randomArr(1000000).sort((a,b)=>{return a-b});

Test runner

Ready to run.

Testing in
TestOps/sec
countOccurrences2
function countOccurrences2(arr, el){
	let result = 0;
	for(let k=0; k<arr.length; k++){
		if(arr[k]===el){
			result++;
		};
	};
	return result;
};

countOccurrences2(input, 1);
ready
countOccurrences1



function binarySearch(arr,searchedItem){
	// debugger;
	let leftPointer = 0,
		rightPointer = arr.length;

	for(let k=0; k<arr.length;k++){
		let mid = Math.floor((rightPointer+leftPointer)/2);
		if(searchedItem>arr[mid]){
			leftPointer = mid;
			continue;
		};
		if(searchedItem<arr[mid]){
			rightPointer = mid;
			continue;
		};
		return mid;
	};
	return -1;
};


function countOccurrences1(arr, el){
	let elPosition = binarySearch(arr, el);

	if(elPosition===-1){
		return 0;
	};

	// let counter = 1;

	let leftPointer = elPosition;
		rightPointer = elPosition;

	while(arr[leftPointer]===el){
		leftPointer--;
	};

	while(arr[rightPointer]===el){
		rightPointer++;
	};

	return rightPointer - leftPointer - 1 ;
	
};

countOccurrences1(input,1);
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.