I have published my doc as Public on the Web -- Anyone on the Internet can find and view a long time ago.
But, when I search for the pieces of my published document, Google result is empty. Should I try Bing search?
When does Google search index the Google Docs and Google Drive? If Google does not index the doc then what is the difference between Public on the web and Anyone with link can access?
Google Drive hosted files are not being crawled just because they are public files. The URL of the each file should be included in a website that is being crawled or should be submitted directly to be indexed.
In my humble opinion, the easiest way for a small number of URLs, is to share publicly the URL of your files in tools like Google+, Facebook, Twitter, etc. To learn the "pro" way, see Are you on Google? - Webmasters Tools Help For something in the middle, see Google My Business.
Regarding the difference between, sharing with Anyone in the web and Publishing to the web, the first gives access to the original version, the second to a separate web version, without real time features, the Google Editors tool bar, etc. For further details see Visibility of documents, spreadsheets, and presentations published to the web.