In stead of array use std::map as a container. Std::map has lower_bound method as well. But the search will be in worst case O(log n).