テストしていないけれどこんな感じか?

void *lsearch(const void *key,const void *base,size_t nmemb,size_t size,int (*compar)(const void *,const void *))
{
size_t i;
const unsigned char *pbase=(const unsigned char *)base;

for(i=0;i<nmemb;i++,pbase+=size)
if(!(*compar)(key,pbase))
return pbase;

return NULL;
}