Продолжаю наполнять раздел для начинающих Java программистов полезными статьями. На этот раз мы рассмотрим пример программы бинарного (двоичного) поиска на Java. Известно, что в Java есть стандартный класс java.util.Arrays, в котором уже реализованы разные вариации бинарного поиска binarySearch(), но в этой статье мы напишем свою реализацию этого алгоритма на Java.
Кратко о бинарном поиске
Бинарный или двоичный поиск является одним из классических алгоритмов поиска элементов в отсортированном списке или массиве чисел. Поиск происходит путем деления элементов массива на половины.
Ниже представлена программа, реализующая алгоритм двоичного поиска. Размер и элементы массива будут вводиться пользователем.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
package ua.com.prologistic; import java.util.Arrays; import java.util.Scanner; public class ExampleBinarySearch { public static void main(String args[]) { int counter, num, item, array[], first, last; //Создаем объект Scanner для считывания чисел, введенных пользователем Scanner input = new Scanner(System.in); System.out.println("Введите количество элементов массива: "); num = input.nextInt(); // Создаем массив введенного пользователем размера array = new int[num]; System.out.println("Введите " + num + " чисел"); //Заполняем массив, вводя элементы в консоль for (counter = 0; counter < num; counter++) array[counter] = input.nextInt(); // сортируем элементы массива, так как для бинарного поиска // элементы массива должны быть отсортированными Arrays.sort(array); System.out.println("Введите элемент для бинарного поиска: "); item = input.nextInt(); first = 0; last = num - 1; // метод принимает начальный и последний индекс, а также число для поиска binarySearch(array, first, last, item); } // бинарный поиск public static void binarySearch(int[] array, int first, int last, int item) { int position; int comparisonCount = 1; // для подсчета количества сравнений // для начала найдем индекс среднего элемента массива position = (first + last) / 2; while ((array[position] != item) && (first <= last)) { comparisonCount++; if (array[position] > item) { // если число заданного для поиска last = position - 1; // уменьшаем позицию на 1. } else { first = position + 1; // иначе увеличиваем на 1 } position = (first + last) / 2; } if (first <= last) { System.out.println(item + " является " + ++position + " элементом в массиве"); System.out.println("Метод бинарного поиска нашел число после " + comparisonCount + " сравнений"); } else { System.out.println("Элемент не найден в массиве. Метод бинарного поиска закончил работу после " + comparisonCount + " сравнений"); } } } |
Результат выполнения программы бинарного (двоичного) поиска на Java:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
Введите количество элементов массива: 5 Введите 5 чисел 43 16 70 61 9 Введите элемент для бинарного поиска: 16 16 является 4 элементом в массиве Метод бинарного поиска нашел число после 3 сравнений |
Результат неудачного выполнения бинарного поиска:
|
1 2 3 4 5 6 7 8 9 10 |
Введите количество элементов массива: 3 Введите 3 чисел 65 9 11 Введите элемент для бинарного поиска: 96 96 не найден в массиве Элемент не найден в массиве. Метод бинарного поиска закончил работу после 3 сравнений |
Вот такая простая программа для демонстрации работы двоичного поиска на Java. Следите за обновлениями раздела Начало работы и читайте еще больше статей по Java для начинающих.
Я начинающий программист — вопрос следующего характера, не ругайте, если что не так. Кажется в коде, что то упущено, что то вроде Arrays.sort либо иной реализации сортировки.
Перед бинарным поиском разве массив не должен быть сначала упорядочен?
Код выглядит нерабочим, результат успешности поиска случаен, зависит от того как пользователь ввел данные. Допустим для последовательности i…j,k, где i…j числа по возрастанию, а k<i, при поиске k результат будет всегда неудачен при длине массива более 4.
И судя по пункту Результат выполнения программы бинарного (двоичного) поиска на Java: в вашем уроке
результат 16 был успешно найден, но на позиции 4, хотя он введен 2м, массив все же скорее всего был упорядочен по убыванию, что не отражено в коде(к тому же код примера на приведенных входных данных не работает).
Вы совершенно правы, я упустил этот момент. Обновил статью с пояснениями и вынес бинарный поиск в отдельный метод. Спасибо за комментарий, Вы помогли развитию сайта.
Решение получилось внешне не только рабочим, но на мой взгляд и более изящным(операции сравнения в данном варианте лучше реализованы). Вот только в Output «16 является 4 элементом в массиве», оно будет при данной сортировке(по возрастанию) 2м, а 4 м оно будет при сортировке по убыванию — Arrays.sort(array, Collections.reverseOrder()). Но тогда придется сначала в массиве примитивы int «обернуть» в класс Integer.