Invisible <voi### [at] devnull> wrote:
> find :: (Ord y) => (x -> y) -> y -> IArray x -> (Int,Int) -> Maybe x
> find field target array (base,size)
>    | size <  0 = error "invalid subrange size"
>    | size == 0 = Nothing
>    | size == 1 = if field (array ! base) == target then Just (array ! 
> base) else Nothing
>    | otherwise =
>      let
>        size2 = size `div` 2
>        base2 = base + size2
>      in
>        case compare (field (array ! base2)) target of
>          EQ -> Just (array ! base2)
>          GT -> find field target array (base, size2)
>          LT -> find field target array (base + size2, size - size2)

  Btw, "binary search" all in itself is an ambiguous concept, as it may mean
one of several things depending on the specification:

  1) The algorithm tells whether the element exists in the array or not
(in other words, the return value is a boolean).

  2) The algorithm returns either the found element itself (if it is in the
array) or an index/reference to the element. If there are many elements which
compare equal, it returns one of them.

  3) Like the previous, but if there are many elements which compare equal,
it returns the first one, or the index/reference to the first one.

  Why the difference between 2) and 3) is relevant may not be immediately
obvious, but there are many cases where it is. For example, while the elements
may compare equal, they might have ancillary data that is different (iow.
each element is a key/value pair, where the key is used for the ordering).
Thus it makes a difference which element is returned.

  Also, if an index/reference is returned, it can make a significant
difference whether it's pointing to the first element in a series of equal
elements, or a random element among them. In many algorithms it's important
to get the first element.

  Changing the algorithm so that it always returns an index to the first
element of a range of equal elements (if they are what is being searched)
doesn't change the algorithm much, and it will still be O(log n).

  Sometimes you want the last element in the range of equal values instead,
or even an index to the one-past the last. One obvious use for this is if
instead of wanting just one of the equal elements, you want to know the
whole range. This is often useful.

  So let's see if you can modify the algorithm to conform to the spec:

  "A function which takes an array of sorted elements and a value, and
which returns an index to the first element in the array which is not
smaller than the value, or to the end of the array if the value is larger
than any of the array elements, in O(log n)."

  The algorithm is pretty much the same as the basic "naive" algorithm.
It just requires a tiny bit of fine-tuning.

  And just a slightly more complicated:

  "A function which takes an array of sorted elements and a value, and
which returns an index pair. The first index points to the first element
in the array which is not smaller than the value. The second index points
to the first element in the array which is greater than the value. Naturally
If the value is greater than all the array elements, they both will point
to the end of the array. And naturally all this in O(log n)."

  As stated, getting the range of equal values is sometimes very useful,
which is why it's important to know how to do this.

-- 
                                                          - Warp

Post a reply to this message