module Main where
import Data.List
search t [] = False --t is an item we want to check is an a list. if the list is empty, then obviously it can't contain t
search t (x:xs) | t == x = True -- if the first item in the list is the same as t, then the search returns the result of True
| otherwise = search t xs --if t is not the head of the list, search the rest of the list
bSearch t xs = bSearch' t (mergeSort xs) -- Binary search requires a sorted list, so we search through the sorted list, using t as the item we want to find
bSearch' t [] = False -- same as before
bSearch' t (x:xs) | t == x = True -- same as before
| t < x = pt fst -- since the list is ordered, we can check the first half of the list if t is less than x
| t > x = pt snd --otherwise we can check the second half of the list
where
pt f = bSearch' t $ f $ splitAt ((length xs)`div`2) (x:xs) -- to save time, here is another function that will perform a binary search on the half of the list you want (f)
On the sorting side I implemented the merge sort algorithm; wherein you keep break the list in half until you have pairs or a single and then sort the pairs and then rejoin everything together in the correct order (`merge`) after they've been sorted. This is implemented as `mergeSort`:
mergeSort :: (Ord a) => [a] -> [a] -- this says the sort function takes a list and returns a list. Each element in the list must be an ordered type, like numbers or letters which come in order
mergeSort [] = [] --obviously an empty list is already sorted
mergeSort [a] = [a] -- as well as list with one element
mergeSort [a,b] = order a b -- for a list with 2 elements, order them according to the definition below
mergeSort xs = merge (pt fst) (pt snd) --merge the 2 halves of the sorted lists, this will continue until the original list has been broken up into smaller lists of 1 or 2 elements
where
pt f = mergeSort $ f $ splitAt ((length xs)`div`2) xs
order :: (Ord a) => a -> a -> [a]
order a b | a < b = [a,b] --order a pair of things
| a > b = [b,a] --and return a list in the correct order, that is biggest at the right, and smallest at the left
| a == b = [a,b] --if the 2 items are the same, leave them that way
merge ::(Ord a) => [a] -> [a] -> [a]
merge [] ys = ys --merging the broken up lists back together, an empty list merging with a non-empty list, you just get the nonempty list
merge xs [] = xs -- they need to be in the correct order; same as above
merge xX@(x:xs) yY@(y:ys) | x <= y = x:(merge xs yY) --if x is less than or equal to y,(x and y being the first element in each list) the merged list will have the head of x merged with the rest of the first list and all of the second list
| otherwise = y:(merge xX ys) --same as above but reversed
