binary_search_vs_linear_search.js

/*
Binary search works on sorted arrays. Binary search begins by comparing an element in the middle of the array with the
target value. If the target value matches the element, its position in the array is returned. If the target value is less than
the element, the search continues in the lower half of the array.
 */

const array_1D = [ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 ],
	array_2D = [
		[ 1, 2, 3 ],
		[ 4, 5, 6 ],
		[ 7, 8, 9 ],

		[ 10, 11, 12 ],

		[ 13, 14, 15 ],
		[ 16, 17, 18 ],
		[ 19, 20, 21 ],
	],
	valueToFindIn1DArray = 20,
	valueToFindIn2DArray = 11;

let linearIterationCount_1D = 0,
	binaryIterationCountRecursive_1D = 0,
	binaryIterationCountLoop_1D = 0,
	linearIterationCount_2D = 0,
	binaryIterationCount_2D = 0,
	binaryIterationCountRecursive_2D = 0;

const binarySearchRecursive = ( arr, leftIndex, rightIndex, valueToSearch, eachIterationCallback = ( args ) => {
} ) => {
	// Stop condition.
	if ( rightIndex >= leftIndex ) {
		let mid = leftIndex + Math.floor( (rightIndex - leftIndex) / 2 );

		eachIterationCallback( { arr, leftIndex, rightIndex, mid, valueToSearch } );

		// If the element is present at the middle, return the index.
		if ( arr[ mid ] === valueToSearch )
			return mid;

		// If element is smaller than mid, then it can only be present in left part of the array.
		if ( arr[ mid ] > valueToSearch )
			return binarySearchRecursive( arr, leftIndex, mid - 1, valueToSearch );

		// Else the element can only be present in right part of the array.
		return binarySearchRecursive( arr, mid + 1, rightIndex, valueToSearch );
	}

	// Element not found
	return false;
}

const binarySearchWhile = ( arrayToSearchIn, valueToSearch, eachIterationCallback = ( args ) => {
} ) => {
	let leftIndex = 0;
	let rightIndex = arrayToSearchIn.length - 1;

	do {
		// Find middle between left and right length of the array.
		let mid = Math.floor( (rightIndex + leftIndex) / 2 );

		eachIterationCallback( { arrayToSearchIn, leftIndex, rightIndex, mid, valueToSearch } );

		// If the element is present at the middle, return the index.
		if ( valueToSearch === arrayToSearchIn[ mid ] ) {
			// Found in the middle
			return mid;
		}
		// If element is smaller than mid, then it can only be present in left part of the array.
		else if ( valueToSearch > arrayToSearchIn[ mid ] ) {
			leftIndex = mid + 1;
		}
		// Else the element can only be present in right part of the array.
		else {
			rightIndex = mid - 1;
		}
	} while ( leftIndex <= rightIndex );

	// Not found
	return false;
}

const linearSearch = ( arrayToSearchIn, valueToSearch, eachIterationCallback = ( args ) => {} ) => {
	for ( let i = 0; i < arrayToSearchIn.length; i++ ) {
		eachIterationCallback( { arrayToSearchIn, i, valueToSearch } );

		if ( arrayToSearchIn[ i ] === valueToSearch ) {
			return i;
		}
	}

	return false;
}

let start, end;

console.group( '1D Array' );

start = performance.now();

binarySearchRecursive( array_1D,
	0,
	array_1D.length - 1,
	valueToFindIn1DArray,
	( args ) => ++binaryIterationCountRecursive_1D
);

end = performance.now()

console.log( 'Binary search recursive iteration count', binaryIterationCountRecursive_1D );
console.log( `Execution performance: ${end - start}` );

// ------------------------------------------------

start = performance.now()

binaryIterationCountLoop_1D = binarySearchWhile(
	array_1D,
	valueToFindIn1DArray,
	( args ) => ++binaryIterationCountLoop_1D
);

end = performance.now()

console.log( 'Binary search while iteration count', binaryIterationCountLoop_1D );
console.log( `Execution performance: ${end - start}` );
// ------------------------------------------------

start = performance.now()

linearSearch(
	array_1D,
	valueToFindIn1DArray,
	( args ) => ++linearIterationCount_1D
);

end = performance.now()

console.log( 'Linear search iteration count', linearIterationCount_1D );
console.log( `Execution performance: ${end - start}` );

console.groupEnd();

console.group( '2D Array' );

start = performance.now()

let x,y;

for( x = 0; x < array_2D.length; x++ ) {
	for( y = 0; y < array_2D[ x ].length; y++ ) {
		linearIterationCount_2D++;

		if( array_2D[ x ][ y ] === valueToFindIn2DArray ) {
			break;
		}
	}
}

end = performance.now()

console.log( 'Linear search iteration count', linearIterationCount_2D );
console.log( `Execution performance: ${end - start}` );

// ------------------------------------------------

start = performance.now()

for( x = 0; x < array_2D.length; x++ ) {
	for ( y = 0; y < array_2D[ x ].length; y++ ) {
		if ( binarySearchWhile( array_2D[ x ], valueToFindIn2DArray, () => ++binaryIterationCount_2D ) ) {
			x = array_2D.length;
			break;
		}
	}
}

end = performance.now()

console.log( 'Binary search iteration count', binaryIterationCount_2D );
console.log( `Execution performance: ${end - start}` );

// ------------------------------------------------

start = performance.now()

for( x = 0; x < array_2D.length; x++ ) {
	for ( y = 0; y < array_2D[ x ].length; y++ ) {
		if ( binarySearchRecursive( array_2D[ x ], 0, array_2D[ x ].length - 1, valueToFindIn2DArray, () => ++binaryIterationCountRecursive_2D ) ) {
			x = array_2D.length;
			break;
		}
	}
}

end = performance.now()

console.log( 'Binary search recursive iteration count', binaryIterationCountRecursive_2D );
console.log( `Execution performance: ${end - start}` );

console.groupEnd();

/*
NodeJS output:
1D Array
	Binary search recursive iteration count 1
	Execution performance: 0.09301801025867462
	Binary search while iteration count 18
	Execution performance: 0.08772601187229156
	Linear search iteration count 19
	Execution performance: 0.08420701324939728
2D Array
	Linear search iteration count 20
	Execution performance: 0.004725992679595947
	Binary search iteration count 19
	Execution performance: 0.14186400175094604
	Binary search recursive iteration count 10
	Execution performance: 0.05622400343418121

Browser output:
1D Array
	Binary search recursive iteration count 1
	Execution performance: 0.10000000894069672
	Binary search while iteration count 18
	Execution performance: 0
	Linear search iteration count 19
	Execution performance: 0.10000000894069672
2D Array
	Linear search iteration count 20
	Execution performance: 0.09999999403953552
	Binary search iteration count 19
	Execution performance: 0.10000000894069672
	Binary search recursive iteration count 10
	Execution performance: 0.09999999403953552

  
  GPT:
  	This code defines several functions related to searching for a value in an array: a binary search that can be called recursively, a binary search that uses a while loop, and a linear search. It also defines an array, and sets up some variables to track the number of iterations each search function takes to find a value. The code also uses the performance.now() method to measure the time it takes for each search function to run. It appears that the code is intended to demonstrate the relative efficiency of each search method by comparing the number of iterations and the time it takes to complete.

  leonid vinikov:
	why linear search is faster then binary search?
  GPT:
	Linear search is faster than binary search in the worst case scenario when the value we are looking for is at the end of the array. Because in linear search, the algorithm will search for the value by iterating through the array element by element and returns the result as soon as it finds it. While in binary search, the algorithm will divide the array into two parts, and keep dividing the array into parts until it finds the element, this process takes more time.

	It should be noted that, while linear search is faster in the worst case scenario, it takes much longer to search for a value in a large array than binary search, which has an average case time complexity of O(log n) and worst case of O(n). In other words, if the array size is large, it's more efficient to use binary search over linear search.
 */
 
 // Create an empty array
let hugeArray = [];

// Use a for loop to generate a large number of elements and push them to the array
for (let i = 0; i < 1000000; i++) {
	hugeArray.push( i );
}

binaryIterationCountRecursive_1D = 0;
binaryIterationCountRecursive_1D = 0
binaryIterationCountLoop_1D = 0;

console.group( 'Huge array' );

start = performance.now();

binarySearchRecursive( hugeArray,
	0,
	hugeArray.length - 1,
	590632,
	( args ) => ++binaryIterationCountRecursive_1D
);

end = performance.now()

console.log( 'Binary search recursive iteration count', binaryIterationCountRecursive_1D );
console.log( `Execution performance: ${end - start}` );

// ------------------------------------------------

start = performance.now()

binaryIterationCountLoop_1D = binarySearchWhile(
	hugeArray,
	590632,
	( args ) => ++binaryIterationCountLoop_1D
);

end = performance.now()

console.log( 'Binary search while iteration count', binaryIterationCountLoop_1D );
console.log( `Execution performance: ${end - start}` );
// ------------------------------------------------

start = performance.now()

linearSearch(
	hugeArray,
	590632,
	( args ) => ++linearIterationCount_1D
);

end = performance.now()

console.log( 'Linear search iteration count', linearIterationCount_1D );
console.log( `Execution performance: ${end - start}` );

console.groupEnd();

/*
Huge array
  Binary search recursive iteration count 1
  Execution performance: 0.05667199194431305
  Binary search while iteration count 590632
  Execution performance: 0.02282300591468811
  Linear search iteration count 590652
  Execution performance: 21.110695004463196
  
  leonid vinikov:
	is binary search can help in 2D arrays?

  GPT:
	Binary search can be used to search for a value in a 2D array, but it's typically applied in a slightly different way than with a 1D array. Because a 2D array is an array of arrays, the binary search algorithm needs to take into account both the row and column indices.

	One way to do this is to flatten the 2D array into a 1D array, then use binary search on that. However this means you will lose the row and column indices of the element you are looking for.
	Another way is to use a modified version of binary search that takes into account the indices of the rows and columns.

	For example, you could write a function that performs a binary search on a 2D array by repeatedly dividing the search area into quadrants, and then checking which quadrant the target value is likely to be in based on the values of the elements at the corners of the quadrant. This can be useful when searching for a value in a 2D array that is sorted by row and column, such as a matrix.

	It's important to note that for 2D arrays, the time complexity of binary search will be O(log(m*n)) where m and n are the number of rows and columns respectively.

	In addition, it's also possible to use a linear search when the array is not sorted.
 */