DSXchange

What do you mean by "lookup data set"?

A Lookup File Set includes its own index.

A virtual Data Set does not. However, if you look at the record schema you will note that there are four control columns, including partition number, partition count, and row number; these could be used for a "binary chop" style of algorithm. A hint cache could also be used to "remember" recently accessed key values.

A sparse lookup will use any index on the table.

If it is a lookup file set, you may find it indexed on the key marked.
You can easily find this by passing the main stream with unsorted data. If you get a match for all the input it doesnt read for where it left.
And you can post us your findings.