A method for proving that an algorithm must perform a certain amount of work: supply observations compatible with more than one possible input until enough information has been acquired to distinguish the required outputs. For exact membership in an arbitrary array, answering every inspected location with a value other than the target forces inspection of every location in the absent case, since any uninspected location could contain the target.
New to topics? Read the docs here!