Вы программист Dart и хотите улучшить свои алгоритмические навыки? Не смотрите дальше! В этой статье блога мы погрузимся в мир двоичного поиска в Dart и рассмотрим различные методы его эффективной реализации. Итак, засучим рукава и начнем!

Двоичный поиск – это мощный алгоритм, используемый для поиска определенного значения в отсортированном списке элементов. Он следует подходу «разделяй и властвуй», многократно деля пространство поиска пополам, пока целевой элемент не будет найден. Это делает двоичный поиск значительно быстрее, чем линейный, особенно для больших наборов данных.

Метод 1: итеративный бинарный поиск
Давайте начнем с простой и понятной итеративной реализации бинарного поиска в Dart:

int binarySearch(List<int> sortedList, int target) {
  int low = 0;
  int high = sortedList.length - 1;

  while (low <= high) {
    int mid = (low + high) ~/ 2;

    if (sortedList[mid] == target)
      return mid;
    else if (sortedList[mid] < target)
      low = mid + 1;
    else
      high = mid - 1;
  }

  return -1; // Element not found
}

Метод 2. Рекурсивный бинарный поиск.
Если вы предпочитаете более лаконичный и элегантный подход, вам подойдет рекурсивный бинарный поиск:

int binarySearch(List<int> sortedList, int target, [int low = 0, int high]) {
  if (high == null)
    high = sortedList.length - 1;

  if (low > high)
    return -1; // Element not found

  int mid = (low + high) ~/ 2;

  if (sortedList[mid] == target)
    return mid;
  else if (sortedList[mid] < target)
    return binarySearch(sortedList, target, mid + 1, high);
  else
    return binarySearch(sortedList, target, low, mid - 1);
}

Метод 3: двоичный поиск с помощью компаратора
Что делать, если вам нужно найти определенный элемент в списке пользовательских объектов? Вы можете использовать функцию сравнения, чтобы определить порядок сортировки:

class Person {
  String name;
  int age;
  Person(this.name, this.age);
}
int comparePersons(Person a, Person b) {
  return a.name.compareTo(b.name);
}
int binarySearchWithComparator(List<Person> sortedList, Person target) {
  int low = 0;
  int high = sortedList.length - 1;
  while (low <= high) {
    int mid = (low + high) ~/ 2;
    int comparison = comparePersons(sortedList[mid], target);
    if (comparison == 0)
      return mid;
    else if (comparison < 0)
      low = mid + 1;
    else
      high = mid - 1;
  }
  return -1; // Element not found
}

Метод 4: двоичный поиск с помощью встроенного класса List Dart
Знаете ли вы, что встроенный класс List Dart предоставляет метод бинарного поиска? Он доступен для списков, реализующих интерфейс Comparable:

List<int> sortedList = [1, 3, 5, 7, 9, 11];
int target = 7;
int index = sortedList.binarySearch(target);
if (index >= 0) {
  print("Element found at index $index");
} else {
  print("Element not found");
}

Подведение итогов
Двоичный поиск — это фундаментальный алгоритм, с которым должен быть знаком каждый программист. В этой статье мы рассмотрели несколько методов реализации двоичного поиска в Dart: от базовых итеративных и рекурсивных подходов до более сложных методов с использованием компараторов и встроенных методов.

Включив двоичный поиск в свой код, вы можете значительно повысить эффективность операций поиска, особенно при работе с большими наборами данных. Так что экспериментируйте с этими методами и раскройте возможности бинарного поиска в своих программах Dart!