How to find a telephone number strored in contacts by searching for a substring on iPhone
There is an app for that. :-)

One of the first apps I installed: Contact by Number.

Actually, there are a few others, and this one hasn't been updated since 2008, but it does what you want and has served me well.