Anything quicker than list.Find()?

ID:2320117
 
Dec 1 2017, 2:29 pm
Code:
list/a=list(3000)
return a.Find(text)


Problem description:
I'm assuming this is O(n). Is there a way to turn this into O(log n) or lower if this is a sorted text list?

I was thinking about some possible implementations, but if you have 3000 or so elements, isn't it time to switch to a sorted list? What should I do?
Dec 1 2017, 3:08 pm
 
if((text in a))


Or, if you want a really fast look-up, you can add data like

my_list["string"] = true

if(my_list["string"]) // "string" is in the list.
Dec 1 2017, 4:08 pm
Associative lookup is O(log n)
Find() is O(n)

Just popping that in for clarity as an addendum to Nadrew's post.
Dec 2 2017, 6:14 pm
i need the return value of the index though, so associative lists don't work

unless the list also had integar values containing the index, like say

list("Bob","Tyler")
list["Bob"]=1
list["Tyler"]=2

instead of a.Find("[b]") i could do a["[b]"] maybe.

would this be faster than O(n)?
Dec 3 2017, 1:21 pm
In response to Mista-mage123
 
var/list/L = list("Bob","Tyler","Mark"=list("Age"=10))

L.Find("Bob") //returns 1
L[1] //returns "Bob"
L[3][1] //returns "Age"
L[3]["Age"] //returns 10
var/list/blah = L["Mark"] //stores the value associated with Mark, which happens to be a list
blah["Age"] //returns 10
blah[1] //returns "Age"