Copyright | (c) Ross Paterson 2008 |
---|---|

License | BSD-style |

Maintainer | ross@soi.city.ac.uk |

Stability | experimental |

Portability | portable |

Safe Haskell | Safe |

Language | Haskell98 |

Binary search of a bounded interval of an integral type for the boundary of an upward-closed set, using a combination of exponential and binary search.

- searchFromTo :: Integral a => (a -> Bool) -> a -> a -> Maybe a

# Documentation

searchFromTo :: Integral a => (a -> Bool) -> a -> a -> Maybe a Source

*O(log(h-l))*.
Search a bounded interval of some integral type.

If `p`

is an upward-closed predicate, `searchFromTo p l h == Just n`

if and only if `n`

is the least number `l <= n <= h`

satisfying `p`

.

For example, the following function determines the first index (if any) at which a value occurs in an ordered array:

searchArray :: Ord a => a -> Array Int a -> Maybe Int searchArray x array = do let (lo, hi) = bounds array k <- searchFromTo (\ i -> array!i >= x) lo hi guard (array!k == x) return k