The Ran elaborates at the beginning of the Masechta to explain that on a Torah level either bedika (and destroying) OR bitul work to prevent the violation of בל יראה ובל ימצא. The fact that bitul works alone is explicit in the gemara 4b, the Ran assumes that just as bitul works alone so too bedika (and destroying) works alone. Although there is a girsa in the Rambam explained by the kesef mishna that implies that bitul may only work on chometz that one is not aware of and destroying is necessary for chometz that one is aware of, the Ran rejects this approach. Therefore, on a Torah level one only needs either bedika or bitul. Nonetheless, the Ran explains that the Rabbonon came along and insist that one do both bedika (and destorying) and bitul. The reason that bedika (and destroying) is not sufficient m'drabonon, the gemara 6b explains הבודק צריך שיבטל שמא ימצא גלוסקא יפה ודעתיה עלויה. Meaning that without bitul we are concerned that you may find a loaf of bread or cake and be lax from immediately destroying it, causing a violation of בל יראה. The gemara is clear that by being mevatel in addition to the bedika, one avoids this concern of גלוסקא יפה, because even if they don't destroy it immediately, their bitul remains in place and is effective even on this loaf. However, the gemara never explains the other direction. If one is mevatel, why is it also necessary to do bedika?
Tosafos explains that the Rabbonon were concerned that if one relied on bitul alone and maintained the chometz in their physical possession, they would inadvertently come to eat from the chometz. Although we don't find this concern by other form of issurei achila and not even by other forms of issurei hana'ah, Tosafos explains that chazal were extra strict by chometz either because one is accustomed to eating chometz all year, or because they modeled themselves after the Torah that aside from the issur ha'na'ah imposes a "harchaka" type issur to also forbid owning the chometz to even own (Rav Yosef Engel in Lekach Tov has a list of d'oraysa harchakos - this being one of them). The Ran adds that another reason to compel the Rabbonon to impose a concern that one will eat it, is because eating chometz is kareis which is more severe than other prohibition (Tzlach explains why Tosafos didn't consider this reason).
Furthermore, the Ran says that chazal imposed the requirement to search and destroy on top of the bitul to ensure that one means the bitul seriously. By taking action to support the bitul, it is clear that the bitul is no mere lip service but one really means what they are saying. The bedika essentially supports the bitul and makes sure that one is serious about it.
Another approach as to why Chazal imposed bedika even after bitul is cited by the Bartenura. He writes that we don't rely on bitul alone because there is a concern that one will find a nice loaf of bread and retract from his bitul. This approach if very difficult because it seems to be contradicted from the gemara. The gemara 6b implies that שמא ימצא גלוסקא יפה is only a concern when one does bedika without bitul, but bitul avoids this concern. According to the Bartenura, this is a concern when only doing bitul and is somehow avoided by the addition of bedika!
The Rashash and Chasam Sofer both offer approaches to explain the Bartenura. The Rashash writes that if one were to merely do bitul it would be very common to find a nice loaf and therefore there is a concern that after finding loaf after loaf, they will eventually retract from their bitul. By imposing bedika they reduced the chances of finding a גלוסקא יפה. Nevertheless, the gemara says that by just doing bedika we are still afraid that one will find a loaf and procrastinate before destroying it. Bitul helps to avoid the violation during that procrastination. The Chasam Sofer (chiddushim) explains that really the Bartenura agrees with Tosafos that if one just does bitul we are concerned they will find a loaf and want to eat it, just that Tosafos says that the concern is that they will actually eat it, and the Bartenura holds the concern is that the interest in eating it will in and of itself be a retraction of the bitul. By imposing bedika, the bitul itself is strengthened because it reminds a person not to be zocheh in the chometz and not to retract from the bitul. Yet, bedika alone isn't enough because one can then violate by finding a loaf even without intending to be zocheh in it, but by doing bitul they avoid that. According to the Bartenura, both bedika without bitul and bitul without bedika cause us to be concerned for שמא ימצא גלוסקא יפה, but doing both avoids the concern.