Logo

Programming-Idioms

This language bar is your friend. Select your favorite languages!
  • Haskell

Idiom #124 Binary search for a value in sorted array

Write the function binarySearch which returns the index of an element having the value x in the sorted array a, or -1 if no such element exists.

binSearch :: Ord a => a -> [a] -> Maybe Int
binSearch _ [] = Nothing
binSearch t l = let n = div (length l) 2
                    (a, m:b) = splitAt n l in
                if t < m then binSearch t a
                else if t > m then aux (binSearch t b)
                else Just n where
    aux :: Maybe Int -> Maybe Int
    aux (Just x) = Just (x+n+1)
    aux _ = Nothing

Haskell promotes using data structures rather than special values to indicate failures, so I have opted to use Maybe rather than return -1. aux serves to add Maybes together.

Ord is used to allow use of < and >.

t is the target to search for and l is the list.
#include <vector>
template<typename T>
int binarySearch(const std::vector<T> &a, const T &x)
{
    if(a.size() == 0) return -1;

    size_t lower = 0;
    size_t upper = a.size() - 1;

    while(lower <= upper)
    {
        auto mid = lower + (upper-lower) / 2;

        if(x == a[mid])
        {
            return (int)mid;
        }
        else if(x > a[mid])
        {
            lower = mid + 1;
        }
        else
        {
            upper = mid - 1;
        }
    }

    return -1;
}

Check for an empty vector up front, otherwise size() will return an unsigned 0, and subtracting 1 will be a big number!

New implementation...
< >
programming-idioms.org