Assume a list of objects with properties P1, P2, ... , Pk which is sorted using those properties.
Each property can be either a known value or a wildcard (*)

You have a set of properties S.

Is there a better method to determine if an object with properties that match S exists in the list other than linear search?

I know that without wildcards, it's a simple binary search with multiple keys, but wildcards tend make binary search difficult to implement as far as I can see.

Example:

You have the list

P1 P2 P3 Obj
1  1  3   A
1  5  2   B
3  2  6   C
5  4  2   D
5  *  2   E
*  *  *   F

the property set (5  3  3) which matches F

the property set (5  3  2) would match E

the property set (3  2  6) would match C