# 38b26bcf2180fb6ad6f7ded472ff76bf16708e2e997d45d61e4c29bddd8a523a Elan 1.8.0 guest default_profile valid

main
  let fruit be example
  print binarySearch(fruit, "lime")
  print binarySearch(fruit, "orange")
end main

function binarySearch(li as ListImmutable<of String>, item as String) returns Boolean
  variable result set to false
  if li.length() > 0 then
    let mid be (li.length()/2).floor()
    let value be li[mid]
    if item is value then
      set result to true
    else if item.isBefore(value) then
      set result to binarySearch(li[..mid], item)
    else
      set result to binarySearch(li[mid + 1..], item)
    end if
  end if
  return result
end function

test 
  let li1 be {"lemon", "lime", "orange"}
  assert binarySearch(li1, "lemon") is true
  assert binarySearch(li1, "lime") is true
  assert binarySearch(li1, "orange") is true
  assert binarySearch(li1, "pear") is false
  let li2 be {"lemon", "orange"}
  assert binarySearch(li2, "lemon") is true
  assert binarySearch(li2, "orange") is true
  assert binarySearch(li2, "pear") is false
  let li3 be {"lemon"}
  assert binarySearch(li3, "lemon") is true
  assert binarySearch(li3, "lime") is false
  let li4 be empty ListImmutable<of String>
  assert binarySearch(li4, "pear") is false
end test

constant example set to {"apple", "avocado", "banana", "blueberry", "cherry", "fig", "grape", "kiwi", "lemon", "lychee", "mango", "orange", "papaya", "peach", "pear", "pineapple", "plum", "raspberry", "strawberry", "watermelon"}
