Заметили ошибку ?
Выделите это место и нажмите Ctrl + Q

Задача по информатике - поиск элемента в массиве.


Всем привет! Настало время позаниматься Информатикой.


Задача: Написать программу, которая ищет индекс элемента в отсортированном по возрастанию массиве целых чисел. На вход подаётся значение элемента, программа выводит индекс этого элемента, если такой элемент имеется в массиве. Если такого элемента нет в массиве, программа должна вывести сообщение. Если таких элементов несколько, вывести индекс любого найденного элемента.


Данная задача отлично подходит для изучения и закрепления темы "Массивы" на уроках Информатики в 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 раза. И т.д.


Сдвигаем левую границу поиска. Теперь наш диапазон [9:19].Ищем середину диапазона: index = (9+19)/2 = 14
14-ый элемент это 63. Не равно нашему искомому 59.

Т.к. 59<63, то сдвигаем правую границу поиска. Теперь наш диапазон [9:14]. Ищем середину диапазона. Берём index = (9+14)/2 = 11
11-ый элемент не равен 59, значит ищем дальше!

55>59 => Сдвигаем левую границу поиска. Теперь наш диапазон [11:14]. Ищем середину диапазона: index = (11+14)/2 = 12

12-ый элемент опять не равен нашему элементу
55 > 59 => Сдвигаем левую границу. Теперь наш диапазон [12:14]. Ищем середину диапазона: index = (12+14)/2 = 13.

Тринадцатый элемент нам подходит! 59 = 59.
Ответ: 13.

задача по информатике - поиск элемента в массиве


Этот подход намного эффективней, чем сравнивать перебором. Время работы примерно: log2n


Код реализуем на языке 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();
        }

Другие строчки консольного приложения опущены.


На этом всё. Встретимся на других темах информатики. Пока!



06-08-2017 в 10:55:57





Похожая статья:

Задача по информатике. Гуси и кролики.

Всем привет! Сегодня решим задачу по информатике "Гуси и кролики"...

Категория: Алгоритмы  Подкатегория: Задачи
Дата: 15-01-2018 в 16:47:34 0



Оставить коментарий:



Напишите email, чтобы получать сообщения о новых комментариях (необязательно):


Задача против робота:

Ответ:


Последние
видео:



Шейкер-сортировка (С#)
ОГЭ по информатике. Задание 18


Подготовка к
ОГЭ


Подготовка к ОГЭ по информатике


Давайте
дружить!


Группа Вконтакте Code-Enjoy

Твиттер Александра Калужского

YouTube канал Code-Enjoy