By all means hit every bank you come across. I have "hit" literally hundreds of different banks in many different towns, and have only been asked if I had an account 4-5 times. I always answered honestly. I was always able to get the halves regardless of whether I had an account or not. For the most part, half dollars are a nuisance to the tellers. They are THRILLED to get rid of them. Usually a bank has to have a certain amount (usually $500 or $1000) before they can "ship them off to the Fed." For most banks (at least in my area) it can take years for the bank to accumulate enough to ship off. Therefore, they have to count them every day...week after week...month after month. They want rid of them. Essentially, you are doing them a favor.
Should you come across a bank that is reluctant to sell them to you, assure them that they will NOT be getting them back. Tell them you're a coin collector from out of town and that the halves will be going back with you. That should do the trick. I'm sure you already know this but NEVER buy halves from a bank, pluck all the keepers, and return them to the same bank.
Hope this helps! Good luck!