Is there a client/API library that provides search of Debian packages, so I can search programatically?
Apt itself is built in C++ and provides some libraries for this in libapt-pkg6.0
There are Perl bindings in libapt-pkg-perl and Python ones in python-apt.
... But the simple and obvious thing is to just use https://packages.debian.org/ and/or run apt-search and friends locally (dctrl used to be nice, but I haven't checked it out in a long time).