IIRC, the main thing holding stuff like this back are generalized collection traits and the main reason we don't have those is the lack of HKT.
See the following for a relevent discussion (it doesn't explicitly mention binary search but that would probably be added to the SortedSet trait):