http://www.linux.or.jp/JM/html/LDP_man-pages/man3/bsearch.3.html

これを見る限り、bsearchは必ずバイナリサーチで実装することとなっているみたいですが、
規格上もそうなっていますか？
整列した配列から探索するのでバイナリサーチ以外の探索法を使う人はいないと思いますが。