# f356846c390824b4cee4239f50c915b5a535f812849d9e4c1dac379b2e2caca5 Elan 1.6.2 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() div 2
    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"}
