Решение задач четвертого класса
Поиск элемента в массиве является наиболее часто встречающимся алгоритмом. Задача заключается в поиске среди элементов одномерного массива элемента, равного заданному «аргументу поиска» a. Существует много вариантов решения этой задачи.
Вариант 1 (линейный поиск). Если нет дополнительной информации о разыскиваемых данных, то остается простой последовательный просмотр массива с увеличением шаг за шагом той его части, где искомого элемента не обнаружено. Такой метод называется линейным поиском. Исходными данными для решения задачи является массив чисел. В результате получаем либо номер элемента, совпадающего с А, либо ответ: «Такого элемента нет». Решение этой задачи может закончиться по двум причинам: 1) перебрали все элементы массива и не нашли нужного элемента; 2) в процессе перебора обнаружился элемент, совпавший с А. В этом случае перебор прекращается и формируется ответ.
Первую причину окончания можно определить, проверив условие: i >= n, где i - текущий элемент массива, n - количество элементов в массиве.
Вторая причина имеет два значения: «найдено» или «не найдено», поэтому ее можно изображать логическим значением, где true соответствует найдено, а false - не найдено.
Таким образом, условие окончания поиска может быть записано в виде (i>=n-1) || f, что соответствует фразе русского языка: «Просмотрены все элементы или не найдено». Просмотр элементов массива в цикле будет выполняться в случае ложности приведенного условия. Найдем его отрицание, воспользовавшись законом де Моргана: отрицание дизъюнкции равно конъюнкции отрицаний.
!((i>=n) || f) = = !(i>=n) && ! f = = (i<n) && ! f.
// линейный поиск элемента в одномерном массиве
const int nn=12; //константа задает максимальный размер массива
int []b=new int b[nn];// исходный массив
int n ; // размер массива
int a; // число для поиска
int i; // индекс массива
bool f ; //истина, если искомый элемент найден
i=0; // начинаем просмотр с первого элемента
f=false; // пока не найдено
while ((i<n) && ! f)
// просматриваем массив, пока есть элементы и не найден искомый
if (b[i]= =a) // если совпали,
f=true // то нашли,
else i++; // иначе перейти к следующему элементу
if f // вывод результатов поиска
Console.WriteLine(«Номер найденного элемента»+i);
else Console.WriteLine(«Не нашли»);
Тестирование.
Тест 1. n=8, B[0]=2, B[1]=8, B[2]=3, B[3]=1, B[4]=9, B[5]=2, B[6]=2, B[7]=2, a=5. Результат поиска: «Не нашли».
Тест 2. n=7, B[0]=2, B[1]=8, B[2]=3, B[3]=1, B[4]=9, B[5]=8, B[6]=2, a=8. Результат поиска: «Номер найденного элемента 1».
Вариант 2 (линейный поиск с барьером). В этом варианте программы применяется широко распространенный прием фиктивного элемента, или барьера, расположенного в конце массива. Использование барьера позволяет упростить условие окончания цикла, т.к. заранее ясно, что хотя бы один элемент, равный а, в массиве есть.
// поиск с барьером в одномерном массиве
const int nn=12; //константа задает максимальный размер массива
int []b=new int b[nn];// исходный массив
int n ; // размер массива
int a; // число для поиска
int i; // индекс массива
bool f ; //истина, если искомый элемент найден
b[n+1]=a; //добавили барьер, равный а, в конец массива
i=0; // начинаем просмотр с первого элемента
while (b[i] !=a) i++
// просматриваем массив, пока не найдем
if (i<n) // вывод результатов поиска
Console.WriteLine(«Номер найденного элемента»+i);
else Console.WriteLine(«Не нашли»);
Тестирование.
Тест 1. n=8, B[0]=2, B[1]=8, B[2]=3, B[3]=1, B[4]=9, B[5]=2, B[6]=2, B[7]=2, a=5. Результат поиска: «Не нашли».
Тест 2. n=7, B[0]=2, B[1]=8, B[2]=3, B[3]=1, B[4]=9, B[5]=8, B[6]=2, a=8. Результат поиска: «Номер найденного элемента 1».
Упражнения:
1. Проведите трассировку и запомните оба варианта поиска.
2. Напишите программы поиска, в которых элементы массива перебираются от конца к началу.
Вариант 3 (поиск методом деления пополам, или двоичный поиск). Поиск элемента в одномерном массиве можно значительно ускорить, если предварительно упорядочить (отсортировать) массив. Для поиска массив делится пополам и для сравнения выбирается средний элемент. Если он совпадает с искомым, то поиск заканчивается. Если средний элемент меньше искомого, то все элементы, расположенные левее его, также будут меньше искомого. Следовательно, их можно исключить из дальнейшего поиска, оставив только правую часть массива. Если средний элемент больше искомого, то отбрасывается правая часть, а остается левая. Далее повторяется процедура деления массива пополам и отбор части массива для дальнейшего поиска. Так продолжается до тех пор, пока искомый элемент не будет найден или длина части массива для поиска не станет равной нулю. Каждый раз величина той части массива, где ведется поиск, уменьшается вдвое. Поэтому максимальное число требующихся сравнений равно ]log2N[, где N - количество элементов в массиве.
Рассмотрим пример двоичного поиска.
Искомый элемент a=7. Исходный массив n=16.
Первый шаг поиска:
номер элемента: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15;
массив B={ 1, 3, 5, 6, 7,10,12,14,15,16,20,21,23,25,26,30 };
начальная граница поиска L=0, конечная граница поиска R=15;
середина части поиска i=(L+R) / 2 = 7;
поскольку B[7]=14>a=7, то отбрасываем правую часть: L=0, R=i-1=6.
Второй шаг поиска:
номер элемента: 0 1 2 3 4 5 6;
массив B={ 1, 3, 5, 6, 7,10,12 };
начальная граница поиска L=0, конечная граница поиска R=6;
середина части поиска i=(L+R)/ 2 = 3;
поскольку B[3]=6<a=7, то отбрасываем левую часть: L=i+1=4, R=6.
Третий шаг поиска:
номер элемента: 4 5 6;
массив B={ 7,10,12 };
начальная граница поиска L=4, конечная граница поиска R=6;
середина части поиска i=(L+R) / 2 = 5;
поскольку B[5]=10>a=7, то отбрасываем правую часть: L=4, R=i-1=4.
Четвертый шаг поиска:
номер элемента: 4;
массив B={ 7 };
начальная граница поиска L=4, конечная граница поиска R=4;
середина части поиска i=(L+R)/ 2 = 4;
поскольку B[5]=7= =a=7, то искомый элемент найден в позиции 5.
Фрагмент программы, реализующий двоичный поиск, приведен ниже:
l=0; r=n-1;
f=false; //не найдено
while( (l<=r) && ! f)
{ i=(l+r) / 2;
if (b[i]= =a) f=true; //нашли
else if (b[i]<a) l=i+1; else r=i-1;
}
Тестирование.
Тест 1: a=7, n=15, b={1,3,5,7,9,10,12,14,16,18,21,23,25,27,29}.
Ответ: искомый элемент найден в позиции 3.
Тест 2: a=6, n=15, b={1,3,5,7,9,10,12,14,16,18,21,23,25,27,29}.
Ответ: искомый элемент не найден.