Binary search function

Resources Community Resources
,
1

I made a binary search function for quick table lookups, just like one can be implemented in other languages. Im not sure the use cases for this function, but i think its faster than normal table.find(), at least in bigger tables(i think?).

Anyway, heres the function:

function binsearch(array : {number}, target : number)
	local start_index = 1
	local end_index = #array

	while start_index <= end_index do
		local middle_index = math.floor((start_index + end_index) / 2)
		local middle_value = array[middle_index]

		if middle_value == target then
			return middle_index 
		elseif middle_value < target then
			start_index = middle_index + 1
		else
			end_index = middle_index - 1
		end
	end

	return nil
end

print(binsearch({1, 5, 8, 10, 12}, 10)) -- Prints 4 as 10 is in index 4

it returns nil if the target number is not in the table, and the index of the target number in the table if it is found.

But some rules for binary search:

The table MUST be sorted. Otherwise it wont work properly.
thats basically it i think.

Anyway, let me know if this is useful in any way, thank you!

9 Likes
2

I’ve had use for binary search for getting a random weighted Events or Sponsors. Since the probability of an element can be different from that of another, the intuitive approach is to assign each event a range out of the total weight of every element. Then a random number is generated, and the weight that includes the random number in it’s range is returned.

The reason why binary search is so much faster than table.find() is that, with table.find(), as the table grows, the time it takes to find the element also grows, linearly. So for example, if the amount of elements in the table doubles, the time it takes will also double.
With binary search, this is not the case, because it is able to exclude a large amount of values, by looking at the element in the center, and discarding every element above, or below, in the table, since the table is sorted. This means that if you double the size of the table, it only adds 1 step to the searching process

This is the concept of Time Complexity, how execution time of algorithms scales relative to input size

And yes, for small tables, time complexity doesn’t mean anything, and table.find() is likely faster

My own implementation of binary search uses recursion, but I see that it can totally be done with a while loop which I should do. One of my implementation also suffers from infinite recursion in very rare cases that I have not been able to replicate consistently…

1 Like
3

I know, i think binary search has a time complexity of O(log n), which is faster than O(n) or a linear approach. I just wanted to improve my scripting skills, and see if things that are usually found outside roblox can be done in roblox.

I dont know if its useful, maybe just for preformance its better, but again, it has to be sorted for it to work. Probably the only con of this approach.

1 Like
4

This is nice

I was trying to find more general computer science things that weren’t Roblox-specific

I know I’d probably not find many computer science theory implementations in the Roblox community, so I encourage that you do share if you implement other things in a more project-specific way–I’m curious

2 Likes