СВЕТ: СПАСИБО
01-12-2023
Читать статью
Калужский Александр: Задача про Цаплю: https://www.youtube.co..
24-11-2023
Сергей: спасибо большое
Всем привет! Настало время позаниматься Информатикой.
Сегодня мы разберём, что такое бинарный поиск.
Задача: Написать программу, которая ищет индекс элемента в отсортированном по возрастанию массиве целых чисел. На вход подаётся значение элемента, программа выводит индекс этого элемента, если такой элемент имеется в массиве. Если такого элемента нет в массиве, программа должна вывести сообщение. Если таких элементов несколько, вывести индекс любого найденного элемента.
Данная задача отлично подходит для изучения и закрепления темы "Массивы" на уроках Информатики в 10 классе.
Решение: Задачу мы будем решать с помощью бинарного поиска (или метода деления пополам, или дихотомии). Данный метод работает только в отсортированном массиве. Этот метод заключается в том, что мы отсекаем по половине нашего диапазона поиска, пока не найдем нужный элемент. Поэтому и метод называется бинарный поиск, из-за того ,что диапазон поиска с каждым проходом уменьшается в два раза.
Пусть у нас есть отсортированный массив:
myArr[0] = 3; myArr[1] = 23; myArr[2] = 24; myArr[3] = 35; myArr[4] = 36; myArr[5] = 44; myArr[6] = 47; myArr[7] = 49; myArr[8] = 51; myArr[9] = 53; myArr[10] = 54; myArr[11] = 55; myArr[12] = 55; myArr[13] = 59; myArr[14] = 63; myArr[15] = 63; myArr[16] = 64; myArr[17] = 67; myArr[18] = 78; myArr[19] = 90;
Нам, к примеру, надо найти индекс элемента, значение которого равно 59.
Для начала найдём середину массива: index = (19+0)/2 = 9 (округляем в меньшую сторону)
Если бы мы попали в наш элемент, то сразу бы вывели ответ. Но у 9-ого индекса значение 53. У нас 53 < 59. Т.к. массив отсортирован по возрастанию, то значит наш элемент находится в той половине, где числа >=53, т.е. в правой половине массива. И теперь все действия необходимо повторить для правой половинки.
Опять ищем середину, но теперь для правой половинки. Проверяем средний элемент. Если попали, то печатаем ответ. Если нет, то сравниваем наш средний элемент правой половинки с искомым элементом, и опять сокращаем диапазон поиска в 2 раза. И т.д.
Код реализуем на языке C#. Данный язык отлично подходит для изучения информатики в школе.
Чтобы наш алгоритм был немного эффективней, при сдвиге левой границы будем добавлять единицу, при сдвиге правой отнимать единицу. Также это позволить более удобно задать условие для основного цикла.
static void Main(string[] args) { // Объявляем массив int[] myArr = new int[20]; // Инициализируем каждый элемент массива myArr[0] = 3; myArr[1] = 23; myArr[2] = 24; myArr[3] = 35; myArr[4] = 36; myArr[5] = 44; myArr[6] = 47; myArr[7] = 49; myArr[8] = 51; myArr[9] = 53; myArr[10] = 54; myArr[11] = 55; myArr[12] = 55; myArr[13] = 59; myArr[14] = 63; myArr[15] = 63; myArr[16] = 64; myArr[17] = 67; myArr[18] = 78; myArr[19] = 90; int left = 0; // Левая граница поиска int right = myArr.Length - 1; // Правая граница поиска int index = 0; // индекс, указывающий середину отрезка int q = Convert.ToInt32(Console.ReadLine()); // Запрашиваем искомое число. int res = -1; // Конечный результат. while(left <= right) { index = (right + left) / 2; ///Узнаем середину отрезка, округляем в меньшую сторону. // Если мы нашли искомый элемент, записываем результат и выходим из цикла. if (myArr[index] == q) { res = index; break; } // Меняем границы. if(myArr[index] < q) { left = index+1; } else { right = index-1; } } if( res != -1) { Console.WriteLine("Искомый индекс: " + res); } else { Console.WriteLine("Такого элемента нет в массиве"); } Console.ReadKey(); }
Другие строчки консольного приложения опущены.
На этом всё. Встретимся на других темах информатики. Пока!