# a5d8d29f4e3f1f29776304a0d9a2a4020c43c3c4707e0559833b1f7d0c2170c7 Elan 1.6.4 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"}
