Can users in the same group have different search permissions?

Yes. For example by default users in group A can search only users in group A. But user ‘User-01’ (member of group A) is configured to search for group B. Then ‘User-01’ can search for group A and B.