gistfile1.txt

trait BinarySearchMethods<T: Ord Eq> {
    pure fn binary_search(&self, &T) -> Option<&self/T>;
    pure fn binary_search_index(&self, &T) -> Option<uint>;
}

impl<T: Ord Eq> &[T]: BinarySearchMethods<T> {
    pure fn binary_search(&self, key: &T) -> Option<&self/T> {
        match self.binary_search_index(key) {
            None => None,
            Some(i) => Some(&self[i])
        }
    }

    pure fn binary_search_index(&self, key: &T) -> Option<uint> {
        let mut low : uint = 0;
        let mut high : uint = self.len()-1;

        while (low <= high) {
            // http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
            let mid = (low + high) >> 1;
            let midv = &self[mid];

            if (midv < key) {
                low = mid + 1;
            } else if (midv > key) {
                high = mid - 1;
            }
            else {
                return Some(mid);
            }
        }
        return None;
    }
}