Бинарный поиск на Java — итеративный и рекурсивный варианты

Двоичный поиск (Binary Search) — это очень быстрый алгоритм поиска элемента в отсортированном массиве. Главное условие — массив должен быть заранее отсортирован. Идея в том, чтобы каждый раз делить область поиска пополам.

Идея алгоритма:

1. Берём средний элемент массива.

2. Если он равен искомому — мы его нашли, возвращаем индекс.

3. Если искомый элемент больше среднего — продолжаем поиск только в правой половине (левую отбрасываем).

4. Если искомый меньше среднего — продолжаем поиск только в левой половине.

5. Повторяем шаги 1-4, пока не найдём элемент или область поиска не станет пустой.

Примечание

Асимптотическая сложность:

• Время: O(log n) — каждый шаг сокращает область поиска вдвое.

• Память (итеративная версия): O(1).

• Память (рекурсивная версия): O(log n) — на стек рекурсии.

• Обязательное условие: массив должен быть отсортирован!

Совет

Чтобы оценить скорость двоичного поиска: в массиве из 1 000 000 элементов линейный поиск в худшем случае сделает миллион сравнений, а двоичный — всего около 20. Это огромная разница.

Предупреждение

Двоичный поиск не работает на неотсортированных массивах. Если массив не отсортирован — сначала отсортируйте его, а потом ищите. Но если поиск нужен только один раз, проще сделать линейный поиск за O(n), чем сначала сортировать за O(n log n).

Чтобы понять этот пример, нужно знать следующие темы Java: цикл while и do…while в Java, оператор if…else в Java, массивы в Java.

Пример: программа на Java для реализации двоичного поиска (итеративная версия)

import java.util.Scanner;

// Binary Search in Java

class Main {
  int binarySearch(int array[], int element, int low, int high) {

    // Repeat until the pointers low and high meet each other
    while (low <= high) {

      // get index of mid element
      int mid = low + (high - low) / 2;

      // if element to be searched is the mid element
      if (array[mid] == element)
        return mid;

      // if element is greater than mid element
      // search only the right side of mid
      if (element > array[mid])
        low = mid + 1;

      // if element is less than mid element
      // search only the left side of mid
      else
        high = mid - 1;
    }

    return -1;
  }

  public static void main(String args[]) {

    // create an object of Main class
    Main obj = new Main();

    // create a sorted array
    int[] array = { 3, 4, 5, 6, 7, 8, 9 };
    int n = array.length;

    // get input from user for element to be searched
    Scanner input = new Scanner(System.in);

    System.out.println("Enter element to be searched:");

    // element to be searched
    int element = input.nextInt();
    input.close();

    // call the binary search method
    // pass arguments: array, element, index of first and last element
    int result = obj.binarySearch(array, element, 0, n - 1);
    if (result == -1)
      System.out.println("Not found");
    else
      System.out.println("Element found at index " + result);
  }
}

Вывод:

Enter element to be searched:
6
Element found at index 3

Здесь мы использовали класс Scanner для ввода данных от пользователя. На основе пользовательского ввода мы применили двоичный поиск, чтобы проверить, присутствует ли элемент в массиве.

Также мы можем использовать рекурсивный вызов для решения той же задачи.

Рекурсивная версия двоичного поиска:

int binarySearch(int array[], int element, int low, int high) {

  if (high >= low) {
    int mid = low + (high - low) / 2;

    // check if mid element is searched element
    if (array[mid] == element)
      return mid;

    // Search the left half of mid

    if (array[mid] > element)
      return binarySearch(array, element, low, mid - 1);

    // Search the right half of mid
    return binarySearch(array, element, mid + 1, high);
  }

  return -1;
}

Здесь метод binarySearch() вызывает сам себя до тех пор, пока элемент не будет найден или условие if не окажется ложным.

Подсказка

Обратите внимание на формулу int mid = low + (high - low) / 2; вместо более очевидной (low + high) / 2. Это защита от переполнения int: если low и high очень большие, их сумма может выйти за пределы типа int, а первый вариант это переполнение исключает.