How can a set offer better search performance than an array
I think the key is that NSSets aren't required to "maintain order," meaning that you cannot access elements with an index, nor can you extract elements in any particular order.  Because NSSets don't offer those kinds of accesses the implementation is free to use hashing, trees or anything else that gives speedier membership checks.