SearchBin is a fast commandline program for searching within binary files. It's a bit like grep for binaries. It offers wildcard matching and has three capabilities for searching: for bytes using hexidecimal, for a plain text string, and for a smaller binary file. Any discovered matches will print the found offsets (0-based).
Bviplus is a console ncurses based binary file editor (hex editor) with Vim-like keys and features. It can quickly open/edit/save very large files (> 2GiB). It can perform regexp-like pattern searches in hex or ASCII windows. It features search highlighting, multiple undo/redo, a tabbed multiple file interface, visual selection, cut and paste (which works between files as well), blob coloring, and more. It can run external programs on selected data, supporting any program that reads stdin and writes stdout. It has few dependencies for easy portability.