Spax's note-finding method for stepmania

findNote_binarysearch_NotITG.lua

steps = P1:GetNoteData()

function findNote(beat, type)
	if not type then type = 'notes' end
	local t = {}
	local r = 0.02
	local left = 1
	local right = #steps
	while left <= right do
		local mid = math.floor((left + right) * 0.5)
		if beat-r <= steps[mid][1] and beat+r >= steps[mid][1] then
			local index = mid
			while index > 1 and beat-r <= steps[index-1][1] and beat+r >= steps[index-1][1] do
				index = index - 1
			end
			t.index = index
			local lengths = {}
			while beat-r <= steps[index][1] and beat+r >= steps[index][1] do
				local steptype = steps[index][3]
				local step = steps[index][2]
				if type == 'notes' then
					if steptype == 1 or steptype == 2 or steptype == 4 then
						t[#t+1] = step
					end
				elseif steptype == type or type == -1 then
					t[#t+1] = step
				end
				lengths[#lengths+1] = steps[index].length or 0
				index = index + 1
			end
			t.lengths = lengths
			return t
		elseif beat-r > steps[mid][1] then
			left = mid + 1
		else
			right = mid - 1
		end
	end
	return t
end

findNote_binarysearch_old.lua

steps = P1:GetNoteData()

function findNote(beat)
	local t = {}
	local r = 0.02
	local left = 1
	local right = #steps
	while left <= right do
		local mid = math.floor((left + right) * 0.5)
		if beat-r <= steps[mid][1] and beat+r >= steps[mid][1] then
			local index = mid
			while index > 1 and beat-r <= steps[index-1][1] and beat+r >= steps[index-1][1] do
				index = index - 1
			end
			t.index = index
			while beat-r <= steps[index][1] and beat+r >= steps[index][1] do
				t[#t+1] = steps[index][2]
				index = index + 1
			end
			return t
		elseif beat-r > steps[mid][1] then
			left = mid + 1
		else
			right = mid - 1
		end
	end
	return t
end

findNote_binarysearch_OutFox.lua

function findNote(beat, type)
	if not type then type = 'notes' end
	local t = {}
	local r = 0.02
	local left = 1
	local right = #steps
	while left <= right do
		local mid = math.floor((left + right) * 0.5)
		if beat-r <= steps[mid][1] and beat+r >= steps[mid][1] then
			local index = mid
			while index > 1 and beat-r <= steps[index-1][1] and beat+r >= steps[index-1][1] do
				index = index - 1
			end
			t.index = index
			local lengths = {}
			while beat-r <= steps[index][1] and beat+r >= steps[index][1] do
				local steptype = steps[index][3]
				local step = steps[index][2]
				if type == 'notes' then
					if steptype == 'TapNoteType_Tap' or
						steptype == 'TapNoteSubType_Hold' or
						steptype == 'TapNoteSubType_Roll' or
						steptype == 'TapNoteType_Lift'
					then
						t[#t+1] = step
					end
				elseif steptype == type or type == -1 then
					t[#t+1] = step
				end
				lengths[#lengths+1] = steps[index].length or 0
				index = index + 1
			end
			t.lengths = lengths
			return t
		elseif beat-r > steps[mid][1] then
			left = mid + 1
		else
			right = mid - 1
		end
	end
	return t
end

findNote_linearsearch_old.lua

function findNote(beat)
	local t = {}
	local r = 0.02
	for i,stepData in ipairs(steps) do
		if beat-r <= stepData[1] and beat+r >= stepData[1] then
			t.index = i
			local index = 0
			while beat-r <= stepData[1] and beat+r >= stepData[1] do
				t[#t+1] = stepData[2]
				index = index + 1
				stepData = steps[i+index]
			end
			return t
		end
	end
	return t
end