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.0 3   A
10 5.2 2   B
3  0.2 68  C
87 4.1 2   D
5  *   2   E
*  *   *   F

the property set (5  3.0  3) would match F

the property set (5  3.0  2) would match E

the property set (3  0.2  68) would match C