pf_lower_bound Interface

public interface pf_lower_bound

The first position at which target could be inserted into an already-sorted values without breaking its order -- i.e. the first element not ordered BEFORE it.

pos lands in 1 .. size(values)+1; it is size(values)+1 when every element is ordered before the target. Together with pf_upper_bound it brackets every element equal to the target, which is what pf_equal_range returns in one call.

values is checked for sortedness first, and that check is O(n). Searching an unsorted array returns a plausible index with no symptom at all, so the check is on by default. Check once with pf_is_sorted and pass assume_sorted=.true. in a loop:

call pf_is_sorted(v, ok)                       ! O(N), once
do k = 1, m
    call pf_lower_bound(v, targets(k), pos, assume_sorted=.true.)   ! O(log N) each
end do

descending/nulls_first must describe the order values is ACTUALLY in -- they select the comparison, they do not reorder anything.

Module Procedures