I wouldn't work in a place that did this. Sorry, but until i give you reason to ask to search me, you're not going to.
I bet this is in their employee manual where employee has to sign when he/she employs by them. Therefore, they have the right to search anyone prior of leaving shift.