Найти минимальное и максимальное значения в массиве в C++
В этом посте мы обсудим, как найти минимальный и максимальный элемент массива в C++.
1. Наивное решение
Наивное решение — написать собственную процедуру для этой простой задачи. Идея состоит в том, чтобы линейно пройти массив, используя простой цикл for или цикл for на основе диапазона. Затем для каждого обнаруженного элемента мы сравниваем его с минимальным или максимальным элементом, найденным до сих пор, и заменяем максимальный элемент, найденный до сих пор, текущим элементом, если он меньше по значению, и минимальный элемент, найденный до сих пор, текущим элементом, если он больше по стоимости.
Найти наименьший элемент массива
Задача 2.49
Дан одномерный массив А неупорядоченных целых чисел. Вывести на экран числа массива, а также найти и вывести на экран наименьшее значение для всех элементов массива. Также вывести номер (индекс) наименьшего элемента в массиве.
Первым делом обращаем внимание на то, что массив не упорядочен (не отсортирован). То есть значения элементов в массиве хранятся “как попало”.
Соответственно, такой массив надо создать. Способа два: вводить значения элементов вручную, либо создать массив программно. Разумеется, сделаем это программно — заполним массив случайными значениями.
Второе — в массиве целые числа. Но целые числа могут быть также и отрицательными. Поэтому при заполнении массива случайными числами это желательно предусмотреть.
Поиск наименьшего значения в массиве
Теперь о том, как будем искать. Есть два относительно простых способа:
- Отсортировать массив по возрастанию значений. Тогда первый элемент массива будет наименьшим. Однако этот способ сам по себе не слишком простой, к тому же в задаче сказано, что надо получить кроме значения ещё и номер элемента. А при сортировке номера изменятся, и это потеряет смысл (либо придётся запоминать старые номера).
- Перебирать все элементы массива и искать самый меньший.
Мы воспользуемся вторым способом.
Сначала во временной переменной MinA сохраним наибольшее возможное значение типа данных, которому принадлежат элементы массива. Затем будем перебирать все элементы массива и сравнивать его с этим значением. Если значение текущего элемента меньше или равно значению MinA, то в переменную MinA запишем значение текущего элемента. И так далее, пока не переберём все элементы массива.
Почему меньше или равно, а не меньше? Дело в том, что теоретически (хотя и почти невозможно в нашем случае), все элементы массива могут содержать наибольшее значение для выбранного типа данных. И тогда, если проверять на “меньше”, программа не выведет никакой итог (либо придётся усложнять программу).
ПРИМЕЧАНИЕ
Не забывайте, что в С++ индексация массива начинается с нуля.
Поиск k-ого наименьшего элемента
Сегодня на Хабре появилась очень интересная статья, о поиске минимального (максимального) значения на отрезке в массиве. Так как статья оказалось интересной и популярной, я решил с вами поделиться ещё одним алгоритмом поиска в массиве некоторых «специальных» значений.
Наверняка каждому встречалась задача нахождения k-ого наименьшего элемента в массиве. k-ый элемент характеризуется тем, что он больше (или равен) k элементов массива и меньше или равен N-k оставшихся элементов (где N – число элементов в массиве).
Задача нахождения k-ого наименьшего элемента обычно связывается с задачей сортировки, так как очевидный метод нахождения этого элемента состоит в сортировке N элементов и выборе k-ого.
Но мы с вами пойдём немного другим путём. Я предполагаю, что читатели знают, как работает алгоритм быстрой сортировки, но на всякий случай напомню. В массиве выбирается случайный элемент x, и выполнется просмотр массива слева, пока не найдётся элемент a[i]>x, затем выполняется просмотр справа, пока не будет найден элемент a[j]<x. Как только два таких элемента найдены, выполняется их обмен и просмотр продолжается до тех пор, пока индексы i,j не станут равны где-то в середине массива. В результате получается массив левая часть которого содержит элементы <=x, а правая часть содержит элементы >=x. Описанная процедура применяется рекурсивно для левой и правой части и продолжается до тех пор, пока не будет получен полностью отсортированный массив. (Немного подробнее о эффективных алгоритмах сортировки).
Процедура разделения, используемая в быстрой сортировке, даёт потенциальную возможность находить искомый (k-ый) элемент гораздо быстрее.
Этот алгоритм работает следующим образом. На первом шаге вызывается процедура разделения с L=1 и R=N (т.е. разделение выполняется для всего массива), причём в качестве разделяющего значения x выбирается a[k]. После разделения получаются значения индексов i,j такие, что
a[h]<x для всех h<i
a[h]>x для всех h>j
i>j
Здесь возможны три случая:
•Разделяющее значение x оказалось слишком мало. В результате граница между двумя частями меньше нужного значения k. Тогда операцию разделения нужно повторить с элементами a[i]…a[R]. 
•Выбранное значение x оказалось слишком велико. Тогда операцию разделения нужно повторить с элементами a[L]…a[j]. 
•Элемент a[k] разбивает массив на две части в нужной пропорции и поэтому является искомым значением. 
Операцию разделения нужно повторять, пока не реализуется случай 3. Этот цикл выражается следующим фрагментом (прошу прощения за Pascal, но мои ученики пока знают только его):
- procedure Find ( k : integer ) ;
- var
- L , R , i , j : integer ;
- w , x : integer ;
- begin
- L : = 1 ; R : = N ;
- while L<R — 1 do
- begin
- x : = a [ k ] ;
- i : = L ;
- j : = R ;
- REPEAT
- while a [ i ] <x do
- i : = i + 1 ;
- while x<a [ j ] do
- j : = j — 1 ;
- if i< = j then
- begin
- w : = a [ i ] ;
- a [ i ] : = a [ j ] ;
- a [ j ] : = w ;
- i : = i + 1 ;
- j : = j — 1 ;
- end ;
- UNTIL i>j ;
- if j<k then
- L : = i ;
- if k<i then
- R : = j ;
- end ;
- end ;
Если предположить, что в среднем каждое разбиение делит пополам размер части массива, в которой находится искомое значение, то необходимое число сравнений будет N+N/2+N/4+…+1=2N. Это объясняет эффективность приведённой процедуры для поиска медиан и прочих величин, а также объясняет её превосходство над простым методом, состоящем в предварительной сортировке всего массива с последующим выбором k-ого элемента (где наилучшее поведение имеет порядок N*log(N)).
Надеюсь, этот алгоритм поможет вам сделать ваши программы более эффективными и быстрыми. Спасибо за внимание.
Найти минимальный элемент в отсортированном по возрастанию и циклически сдвинутом массиве
Как найти минимальный элемент в полностью отсортированном массиве? Это будет 1й элемент массива. Отлично, но что делать, если отсортированный массив сдвинут циклически? Например, [3, 4, 5, 6, 7, 8, 1, 2]. Массив отсортирован, но сдвинут влево на 2 позиции. Можно ли как-то использовать прежнюю сортировку?!
Разбор задачи
Вывести индекс заданного элемента в отсортированном по возрастанию и циклически сдвинутом массиве
Эта задача похожа на предыдущую, но в данном случае необходимо найти заданный элемент в массиве и вывести его индекс. Посмотрите, как изменить алгоритм прошлой задачи для решения текущей!
Разбор задачи
Найти отсутствующий элемент в массиве
Дан массив, в котором находятся натуральные числа от 1 до N, при этом каждое число представлено только 1 раз, но одно число заменили на 0. Вам необходимо найти это число. Здесь есть несколько вариантов решения: один из этих подходов — математический, другой — с использованием побитовых операций. Вы должны понимать и знать оба варианта, т.к. они помогут вам в решении других практических задач!
Разбор задачи
Преобразование массива путем произведения всех значений
Возможно, вам покажется, что это задача среднего уровня сложности. Однако в реальности ее решение простое, как 2 копейки. Вы же знаете, что массив можно обойти с конца к началу?! Отлично, тогда вы точно её решите!
Разбор задачи
Перестановка чётных/нечётных элементов в массиве
По сути, вам предлагается отсортировать массив по особому правилу: сначала чётные, затем нечётные элементы. Попробуйте сделать свою реализацию! Если не выйдет, смотрите, как выполнить технику перестановки элементов по заданному предикату.
Разбор задачи
Вывести максимальную сумму элементов в массиве
На мой взгляд, ключевая задача в этой подборке. Попробуйте решить её самостоятельно, вот массив [-1, 10, -9, 5, 6, -10]. Необходимо вывести максимальную сумму элементов в массиве.
Разбор задачи
Найти все пары чисел в массиве, сумма которых равна X
Здесь тоже есть несколько способов решения. В нашем разборе вы познакомитесь с техникой двух указателей, двигающихся с разных концов массива, а также с более простым способом — с помощью хэш-функции.
Разбор задачи
Есть ли такие два числа в массиве, перемножив которые мы получим заданное число X
Задача похожа на предыдущую, но здесь вы столкнётесь с более сложной операцией — умножение/деление.
Разбор задачи
Мажоритарный элемент массива — 1
Как найти элемент в массиве, который встречается в массиве более, чем в половине случаев?Заводим хэш-функцию и считаем количество вхождений каждого числа. Всё просто, согласен. А вы знаете, как это сделать без использования доп.О(N) памяти?!
Разбор задачи
Мажоритарный элемент массива — 2
Усложняем предыдущую задачу, теперь необходимо найти все элементы (если такие существуют), которые встречаются в массиве более, чем [N / 3] раз. Решаем эту задачу без использования доп.памяти!
Разбор задачи