content: {-
      MinFree.hs, Find the smallest free number
      Copyright (C) 2011, Liu Xinyu (liuxinyu95@gmail.com)
  
      This program is free software: you can redistribute it and/or modify
      it under the terms of the GNU General Public License as published by
      the Free Software Foundation, either version 3 of the License, or
      (at your option) any later version.
  
      This program is distributed in the hope that it will be useful,
      but WITHOUT ANY WARRANTY; without even the implied warranty of
      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      GNU General Public License for more details.
  
      You should have received a copy of the GNU General Public License
      along with this program.  If not, see <http://www.gnu.org/licenses/>.
  -}
  
  module MinFree where
  
  import Data.List
  
  minFree xs = bsearch xs 0 (length xs - 1)
  
  bsearch xs l u | xs == [] = l
                 | length as == m - l + 1 = bsearch bs (m+1) u
                 | otherwise = bsearch as l m
      where
        m = (l + u) `div` 2
        (as, bs) = partition (<=m) xs
  
  test = minFree [08, 23, 09, 00, 12, 11, 01, 10, 13, 07, 41, 04, 14, 21, 05, 17, 03, 19, 02, 06]