Binary Search (that gives multiple results depending on the matches) for an array of strings!

binarySearchonStrings.js

// this is originally for a search function for my
// twemoji-search Vue app (https://github.com/Makiyu-py/twemoji-search)
// but I found that fuzzy search existed behind my back
// the whole time so I switched to that but I don't
// want this binary search code floating in the wilderness
// of the repo's commit history, so I made this gist!

// btw this is based on Cedric Dugas' own implementation
// of the binary search algorithm on js, I just modified
// it to be "modern" I guess.
// https://github.com/posabsolute/javascript-binary-search-algorithm/blob/master/searchBinary.js

const letterSearchBinary = function (payload) {
	const needle = payload.needle;
	const haystack = payload.haystack;

	if (needle === '') return [];

	let haystackLength = haystack.length;
	let needleLength = needle.length;

	if (typeof haystack === 'undefined' || !haystackLength) return [];

	// get middle position
	let mid;

	let high = haystack.length - 1;
	let low = 0;

	while (low <= high) {
		mid = Math.floor((low + high) / 2);
		let element = haystack[mid].substr(0, needleLength);

		if (element > needle) {
			high = mid - 1;
		} else if (element < needle) {
			low = mid + 1;
		} else {
			mid = mid;
			break;
		}
	}
	if (typeof mid === 'undefined') mid = -1;

	// getting the results
	if (mid === -1) return [];

	let start, end;

	for (let i = mid; i > -1; i--) {
		let element = haystack[i].substr(0, needleLength);
		if (element != needle) {
			start = i + 1;
			break;
		} else {
			start = 0;
		}
	}
	for (let i = mid; i < haystackLength; i++) {
		let element = haystack[i].substr(0, needleLength);
		if (element != needle) {
			end = i;
			break;
		} else {
			end = haystackLength - 1;
		}
	}
	let result = [];
	for (let i = start; i < end; i++) {
		result.push(haystack[i]);
	}

	return result;
};