binary_search.dart

void main() {
  var list = List.generate(1000, (x) => x + 1);
  print('Binary search result: ${binarySearch(list, 213)}');
  print('Binary search recursive result: ${binarySearchRecursive(list, 287)}');
}

/**
 * Returns the index of the found [target].
 */
int? binarySearch(List<int> list, int target) {
  var first = 0;
  var last = list.length - 1;
  while(first <= last) {
    int midpoint = ((first + last) / 2).floor();
    if (list[midpoint] == target) {
      return midpoint;
    } else if(list[midpoint] < target) {
      first = midpoint + 1;
    } else {
      last = midpoint -1;
    }
  }
  return null;
}

/**
 * Returns true if the [target] is found.
 */
bool binarySearchRecursive(List<int> list, int target) {
  if (list.isEmpty) return false; 
  int midpoint = (list.length / 2).floor();
  if (list[midpoint] == target) return true;
  if(list[midpoint] < target) return binarySearchRecursive(list.sublist(midpoint + 1), target);
  return binarySearchRecursive(list.sublist(0, midpoint), target);
}