#!/usr/bin/runghc

module AlgBinarySearch where

import Data.Vector as V

binarySearchWhere :: (Ord a) => V.Vector a -> a -> Int -> Int -> Maybe Int
binarySearchWhere coll element lo hi
  | hi < lo = Nothing
  | pivot < element = binarySearchWhere coll element (mid + 1) hi
  | element < pivot = binarySearchWhere coll element lo (mid - 1)
  | otherwise = Just mid
  where
    mid = lo + div (hi - lo) 2
    pivot = coll V.! mid

binarySearchLet :: (Ord a) => V.Vector a -> a -> Int -> Int -> Maybe Int
binarySearchLet coll element lo hi =
  let mid = lo + div (hi - lo) 2
      pivot = coll V.! mid
   in if hi < lo
        then Nothing
        else case compare pivot element of
          LT -> binarySearchLet coll element (mid + 1) hi
          GT -> binarySearchLet coll element lo (mid - 1)
          EQ -> Just mid

main :: IO ()
main = do
  print (binarySearchWhere (V.fromList [1 .. 30]) 30 0 29)
  print (binarySearchWhere (V.fromList ['a' .. 'z']) 'g' 0 29)
  print (binarySearchWhere (V.fromList [1, 3 .. 30]) 4 0 29)
  putStrLn ""
  print (binarySearchLet (V.fromList [1 .. 30]) 30 0 29)
  print (binarySearchLet (V.fromList ['a' .. 'z']) 'g' 0 29)
  print (binarySearchLet (V.fromList [1, 3 .. 30]) 4 0 29)