Обработка ошибок?
Ексепшен выкинуть, разумеется. Пусть тот, кто вызвал с фиговыми параметрами, сам разбирается что с этим делать.
Если произошла ошибка (в том числе и при поиске), то безусловно исключение (если они есть). Т.е. в случае с поиском, если найти не можем из-за ошибки соединения с БД или некорректных условий поиска.
А если найти не можем из-за того, что элемента нет и это нормальная штатная ситуация, то использовать специальное возвращаемое значение. В языках с динамической типизацией это как правило None, null или подобный тип. Если None может храниться в коллекции и является допустимым возвращаемым значением, то, например в питоне, часто создают класс с именем тип NotFoundError и возвращают тип класса. Он гарантированно не является валидным значением.
В языках со статической типизацией используют либо что-то вроде boost::optional т.е. структуры из значения и флага, либо возвращают указатель/итератор для которого есть специальное пустое значение.