A simple autocomplete proof of concept in Lua which binary searches a sorted array of strings. Also allows for searching for terms with a different word order than the original string (by inserting permutations into array) and permitting alternate spellings/abbreviations by permuting those as well.

autocomplete.lua

-- A cool autocomplete demo
-- @author Validark
-- Strings are stored in a lexigraphically sorted array, which can be binary searched for the first and last element which matches a query

-- Please note the "groupings" functionality is an unvalidated afterthought which may or may not work properly, but overall this code has some nice gems:

-- I was originally thinking that https://github.com/evaera/Cmdr could use this to get O(log n) autocompletes (old algo uses O(n))
-- However, Cmdr is designed in such a way that it creates a new autocomplete function on-demand each time,
-- 	which means we'd have to sort (or at least verify the sortedness) of the most recent data each time (for changing data at least, like a Player list).
-- Sorting at run-time takes O(n*log n) time, making it hard to compete with the old algorithm where the pre-processing step just gets the data in the right format
--	Even though each individual query would be faster with binary search, the difference is hard to make up when you have to pre-process data at run-time

-- Thus, this autocomplete code should be used in places where the data can be sorted ahead of time

-- 1. A Lua implementation of the QuickPerm Algorithm to permute an array of strings in-place (and `table.concat` each one)
-- 2. A proof of concept autocomplete algorithm using binary search(es) on a lexigraphically sorted list
-- 3. Another version of my string.split polyfill

-- polyfills for Roblox built-ins
local typeof = typeof or type
local create = table.create or function(num, val)
	local t = {}
	for i = 1, num do t[i] = val end
	return t
end

local split = string.split or function(str, sep, plain)
	local results = {}
	if sep == "" then
		for i in string.gmatch(str, ".") do
			table.insert(results, i)
		end
	else
		if sep == nil then
			sep = ","
		end

		local pos = 1

		while true do
			local a, b = string.find(str, sep, pos, plain ~= false)
			if a == nil then break end
			table.insert(results, string.sub(str, pos, a - 1))
			pos = b + 1
		end

		table.insert(results, string.sub(str, pos))
	end

	return results
end

local arr = {
	"White", "Grey", "Light yellow", "Brick yellow", "Light green (Mint)", "Light reddish violet", "Pastel Blue",
	"Light orange brown", "Nougat", "Bright red", "Med. reddish violet", "Bright blue", "Bright yellow", "Earth orange",
	"Black", "Dark grey", "Dark green", "Medium green", "Lig. Yellowich orange", "Bright green", "Dark orange",
	"Light bluish violet", "Transparent", "Tr. Red", "Tr. Lg blue", "Tr. Blue", "Tr. Yellow", "Light blue",
	"Tr. Flu. Reddish orange", "Tr. Green", "Tr. Flu. Green", "Phosph. White", "Light red", "Medium red", "Medium blue",
	"Light grey", "Bright violet", "Br. yellowish orange", "Bright orange", "Bright bluish green", "Earth yellow",
	"Bright bluish violet", "Tr. Brown", "Medium bluish violet", "Tr. Medi. reddish violet", "Med. yellowish green",
	"Med. bluish green", "Light bluish green", "Br. yellowish green", "Lig. yellowish green", "Med. yellowish orange",
	"Br. reddish orange", "Bright reddish violet", "Light orange", "Tr. Bright bluish violet", "Gold", "Dark nougat",
	"Silver", "Neon orange", "Neon green", "Sand blue", "Sand violet", "Medium orange", "Sand yellow", "Earth blue",
	"Earth green", "Tr. Flu. Blue", "Sand blue metallic", "Sand violet metallic", "Sand yellow metallic",
	"Dark grey metallic", "Black metallic", "Light grey metallic", "Sand green", "Sand red", "Dark red",
	"Tr. Flu. Yellow", "Tr. Flu. Red", "Gun metallic", "Red flip/flop", "Yellow flip/flop", "Silver flip/flop", "Curry",
	"Fire Yellow", "Flame yellowish orange", "Reddish brown", "Flame reddish orange", "Medium stone grey", "Royal blue",
	"Dark Royal blue", "Bright reddish lilac", "Dark stone grey", "Lemon metalic", "Light stone grey", "Dark Curry",
	"Faded green", "Turquoise", "Light Royal blue", "Medium Royal blue", "Rust", "Brown", "Reddish lilac", "Lilac",
	"Light lilac", "Bright purple", "Light purple", "Light pink", "Light brick yellow", "Warm yellowish orange",
	"Cool yellow", "Dove blue", "Medium lilac", "Slime green", "Smoky grey", "Dark blue", "Parsley green", "Steel blue",
	"Storm blue", "Lapis", "Dark indigo", "Sea green", "Shamrock", "Fossil", "Mulberry", "Forest green", "Cadet blue",
	"Electric blue", "Eggplant", "Moss", "Artichoke", "Sage green", "Ghost grey", "Lilac", "Plum", "Olivine",
	"Laurel green", "Quill grey", "Crimson", "Mint", "Baby blue", "Carnation pink", "Persimmon", "Maroon", "Gold",
	"Daisy orange", "Pearl", "Fog", "Salmon", "Terra Cotta", "Cocoa", "Wheat", "Buttermilk", "Mauve", "Sunrise",
	"Tawny", "Rust", "Cashmere", "Khaki", "Lily white", "Seashell", "Burgundy", "Cork", "Burlap", "Beige", "Oyster",
	"Pine Cone", "Fawn brown", "Hurricane grey", "Cloudy grey", "Linen", "Copper", "Dirt brown", "Bronze", "Flint",
	"Dark taupe", "Burnt Sienna", "Institutional white", "Mid gray", "Really black", "Really red", "Deep orange",
	"Alder", "Dusty Rose", "Olive", "New Yeller", "Really blue", "Navy blue", "Deep blue", "Cyan", "CGA brown",
	"Magenta", "Pink", "Deep orange", "Teal", "Toothpaste", "Lime green", "Camo", "Grime", "Lavender",
	"Pastel light blue", "Pastel orange", "Pastel violet", "Pastel blue-green", "Pastel green", "Pastel yellow",
	"Pastel brown", "Royal purple", "Hot pink"
}

local function id(i)
	return string.rep("\u{200b}", i)
end

local expansions = {
	["med."] = "medium",
	["medi."] = "medium",
	["lig."] = "light",
	["tr."] = "true",
	["flu."] = "fluorescent",
	["phosph."] = "phosphorus",
	["br."] = "bright",
	yellowich = "yellowish",
	metalic = "metallic",
	grey = "gray",
	gray = "grey",
	lg = "light",

	-- we *could* support groupings as well
	yeller = "yellowish" .. id(1),
	magenta = "pinkish" .. id(1),
	rose = "reddish pinkish" .. id(1),
	lavender = "purpleish" .. id(1),
	bluish = "blueish" .. id(1), -- we use this spelling here so that "blue" still retrieves "bluish"
	cyan = "light blueish" .. id(2),
	shamrock = "greenish" .. id(1),
	burgundy = "reddish" .. id(2),
	maroon = "darkish reddish" .. id(3),
	seashell = "pinkish" .. id(1),
	salmon = "pinkish" .. id(2),
	sunrise = "pinkish" .. id(3),
	mauve = "pinkish" .. id(4),
}

local originals = {}
local rearrangedStrings = create(#arr)
-- rearrangedStrings is a processed version of arr where
--	- all letters are lowercase
--	- abbreviations are expanded (hardcoded)
--	- misspellings are corrected (hardcoded)
--	- all resulting entries are duplicated for each possible permutation of space-separated strings (e.g. "faded green" -> "green faded")

for _, v in ipairs(arr) do
	local lower = string.lower(v)
	for base in pairs { [lower] = true, [string.gsub(lower, "%l+%.?", expansions)] = true } do
		originals[base] = v
		table.insert(rearrangedStrings, base)

		-- permute all possible combinations using the QuickPerm Algorithm:
		-- keep in mind this has factorial complexity by design
		-- https://www.quickperm.org/

		local a = split(base, " ")
		local N = #a
		local p = create(N, 1)
		local i = 2
		while i <= N do
			local pi = p[i]
			if pi < i then
				local j = i % 2 == 1 and 1 or pi
				a[j], a[i] = a[i], a[j]

				-- below is not part of QuickPerm
				local rearrangedString = table.concat(a, " ")
				originals[rearrangedString] = v
				table.insert(rearrangedStrings, rearrangedString)
				-- above is not part of QuickPerm

				p[i] = pi + 1
				i = 2
			else
				p[i] = 1
				i = i + 1
			end
		end
	end
end

-- utilize the speed of table.sort without any pesky Lua calls
table.sort(rearrangedStrings)

-- In an array sorted by your targetCondition, this will return the first location where your condition would return true
local function binarySearchFirst(array, targetCondition, left, right)
	while right >= left do
		local mid = left + math.floor((right - left) / 2)
		if targetCondition(array[mid]) then
			right = mid - 1
		else
			left = mid + 1
		end
	end

	return left
end

local function query(queryStr)
	local str = string.lower(queryStr)
	local x = binarySearchFirst(rearrangedStrings, function(mid) return mid >= str end, 1, #rearrangedStrings)
	local y = binarySearchFirst(rearrangedStrings, function(mid) return string.sub(mid, 1, #str) ~= str end, x, #rearrangedStrings)
	local results = {}
	local set = {}
	for i = x, y - 1 do
		local result = originals[rearrangedStrings[i]]
		if not set[result] then -- deduplication
			set[result] = true
			table.insert(results, result)
		end
	end
	return results
end

local t1 = os.clock()
local ans = query("z")
local t2 = os.clock()
print("query of " .. #rearrangedStrings .. " items completed in " .. (t2 - t1))
for i, v in ipairs(ans) do print(i, v) end

--[[
"no" -> ["Nougat", "Dark nougat"]
"gra" -> [
	"Grey", "Cloudy grey", "Dark grey",
	"Dark grey metallic", "Dark stone grey",
	"Ghost grey", "Hurricane grey", "Light grey",
	"Light grey metallic", "Light stone grey", "Medium stone grey",
	"Mid gray", "Quill grey", "Smoky grey"
]
^^ note how we have "Mid gray" as well as all the others that use the "grey" spelling

"pink" -> ["Pink", "Carnation pink", "Hot pink", "Light pink"]
"w" -> ["Warm yellowish orange", "Wheat", "White", "Institutional white", "Lily white", "Phosph. White"]
--]]