Π Π°Π±ΠΎΡ‚Π° с массивами являСтся ΠΎΠ΄Π½ΠΎΠΉ ΠΈΠ· Ρ„ΡƒΠ½Π΄Π°ΠΌΠ΅Π½Ρ‚Π°Π»ΡŒΠ½Ρ‹Ρ… Π·Π°Π΄Π°Ρ‡ Π² ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠΈ ΠΏΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΡ‹ 1Π‘:ΠŸΡ€Π΅Π΄ΠΏΡ€ΠΈΡΡ‚ΠΈΠ΅. Π‘ΡƒΠ΄ΡŒ Ρ‚ΠΎ ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ° Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ΠΎΠ² Π²Ρ‹Π±ΠΎΡ€ΠΊΠΈ ΠΈΠ· Π±Π°Π·Ρ‹ Π΄Π°Π½Π½Ρ‹Ρ…, Ρ„ΠΎΡ€ΠΌΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ слоТных ΠΎΡ‚Ρ‡Π΅Ρ‚ΠΎΠ² ΠΈΠ»ΠΈ Π»ΠΎΠ³ΠΈΠΊΠ° бизнСс-процСссов, Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊΡƒ постоянно приходится ΠΌΠ°Π½ΠΈΠΏΡƒΠ»ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ Π½Π°Π±ΠΎΡ€Π°ΠΌΠΈ Π΄Π°Π½Π½Ρ‹Ρ…. Одной ΠΈΠ· самых частых ΠΏΠΎΠ΄Π·Π°Π΄Π°Ρ‡ Π² этом процСссС являСтся поиск наибольшСго значСния. НСсмотря Π½Π° ΠΊΠ°ΠΆΡƒΡ‰ΡƒΡŽΡΡ простоту, эта опСрация ΠΈΠΌΠ΅Π΅Ρ‚ мноТСство нюансов, Π²Π»ΠΈΡΡŽΡ‰ΠΈΡ… Π½Π° ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ ΠΈ Ρ‡ΠΈΡ‚Π°Π΅ΠΌΠΎΡΡ‚ΡŒ ΠΊΠΎΠ΄Π°.

Π’ экосистСмС 1Π‘ сущСствуСт нСсколько ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ΠΎΠ² ΠΊ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡŽ Π·Π°Π΄Π°Ρ‡ΠΈ поиска максимального элСмСнта. ΠžΡ‚ классичСских Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² с использованиСм Ρ†ΠΈΠΊΠ»ΠΎΠ² Π΄ΠΎ примСнСния соврСмСнных встроСнных Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ языка запросов ΠΈ ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠ² ΠΊΠΎΠ»Π»Π΅ΠΊΡ†ΠΈΠΈ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ. Π’Ρ‹Π±ΠΎΡ€ ΠΊΠΎΠ½ΠΊΡ€Π΅Ρ‚Π½ΠΎΠ³ΠΎ ΠΌΠ΅Ρ‚ΠΎΠ΄Π° зависит ΠΎΡ‚ контСкста: Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚Π΅ Π»ΠΈ Π²Ρ‹ с числами, Π΄Π°Ρ‚Π°ΠΌΠΈ ΠΈΠ»ΠΈ строками, Π° Ρ‚Π°ΠΊΠΆΠ΅ ΠΎΡ‚ Ρ‚Ρ€Π΅Π±ΠΎΠ²Π°Π½ΠΈΠΉ ΠΊ скорости выполнСния ΠΊΠΎΠ΄Π° Π² высоконагруТСнных систСмах.

Π’ этой ΡΡ‚Π°Ρ‚ΡŒΠ΅ ΠΌΡ‹ Π΄Π΅Ρ‚Π°Π»ΡŒΠ½ΠΎ Ρ€Π°Π·Π±Π΅Ρ€Π΅ΠΌ Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Π΅ стратСгии поиска экстрСмума. ΠœΡ‹ рассмотрим, ΠΊΠ°ΠΊ ΠΏΡ€Π°Π²ΠΈΠ»ΡŒΠ½ΠΎ ΠΈΠ½ΠΈΡ†ΠΈΠ°Π»ΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅, ΠΊΠ°ΠΊΠΈΠ΅ Ρ‚ΠΈΠ·Ρ‹ Π΄Π°Π½Π½Ρ‹Ρ… ΠΌΠΎΠΆΠ½ΠΎ ΡΡ€Π°Π²Π½ΠΈΠ²Π°Ρ‚ΡŒ ΠΌΠ΅ΠΆΠ΄Ρƒ собой ΠΈ ΠΊΠ°ΠΊ ΠΈΠ·Π±Π΅ΠΆΠ°Ρ‚ΡŒ распространСнных ошибок ΠΏΡ€ΠΈ Ρ€Π°Π±ΠΎΡ‚Π΅ с пустыми массивами. ПониманиС этих ΠΏΡ€ΠΈΠ½Ρ†ΠΈΠΏΠΎΠ² ΠΏΠΎΠΌΠΎΠΆΠ΅Ρ‚ Π²Π°ΠΌ ΠΏΠΈΡΠ°Ρ‚ΡŒ Π±ΠΎΠ»Π΅Π΅ Π½Π°Π΄Π΅ΠΆΠ½Ρ‹ΠΉ ΠΈ ΠΎΠΏΡ‚ΠΈΠΌΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Π½Π½Ρ‹ΠΉ ΠΊΠΎΠ΄.

ΠšΠ»Π°ΡΡΠΈΡ‡Π΅ΡΠΊΠΈΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ поиска с использованиСм Ρ†ΠΈΠΊΠ»Π°

Π‘Π°ΠΌΡ‹ΠΌ ΡƒΠ½ΠΈΠ²Π΅Ρ€ΡΠ°Π»ΡŒΠ½Ρ‹ΠΌ ΠΈ понятным способом Π½Π°ΠΉΡ‚ΠΈ наибольшСС Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ являСтся ΠΏΠ΅Ρ€Π΅Π±ΠΎΡ€ элСмСнтов массива Π² Ρ†ΠΈΠΊΠ»Π΅. Π­Ρ‚ΠΎΡ‚ ΠΌΠ΅Ρ‚ΠΎΠ΄ Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ Π²ΠΎ всСх вСрсиях ΠΏΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΡ‹ ΠΈ Π½Π΅ зависит ΠΎΡ‚ наличия спСцифичСских Π±ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊ. Π‘ΡƒΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° проста: ΠΌΡ‹ создаСм ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΡƒΡŽ-аккумулятор, присваиваСм Π΅ΠΉ Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅, Π° Π·Π°Ρ‚Π΅ΠΌ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ сравниваСм ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ элСмСнт массива с Ρ‚Π΅ΠΊΡƒΡ‰ΠΈΠΌ максимумом.

ΠšΡ€ΠΈΡ‚ΠΈΡ‡Π΅ΡΠΊΠΈ Π²Π°ΠΆΠ½Ρ‹ΠΌ ΠΌΠΎΠΌΠ΅Π½Ρ‚ΠΎΠΌ здСсь являСтся ΠΏΡ€Π°Π²ΠΈΠ»ΡŒΠ½Π°Ρ инициализация ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΠœΠ°ΠΊΡΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ΅Π—Π½Π°Ρ‡Π΅Π½ΠΈΠ΅. Если Π²Ρ‹ Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚Π΅ с ΠΏΠΎΠ»ΠΎΠΆΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹ΠΌΠΈ числами, ΠΌΠΎΠΆΠ½ΠΎ Π½Π°Ρ‡Π°Ρ‚ΡŒ с нуля. Однако для ΡƒΠ½ΠΈΠ²Π΅Ρ€ΡΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ, особСнно Ссли Π² массивС ΠΌΠΎΠ³ΡƒΡ‚ Π±Ρ‹Ρ‚ΡŒ ΠΎΡ‚Ρ€ΠΈΡ†Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹Π΅ числа ΠΈΠ»ΠΈ Π΄Π°Ρ‚Ρ‹, Π»ΡƒΡ‡ΡˆΠ΅ ΠΏΡ€ΠΈΡΠ²ΠΎΠΈΡ‚ΡŒ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ ΠΏΠ΅Ρ€Π²ΠΎΠ³ΠΎ элСмСнта массива. Π­Ρ‚ΠΎ Π³Π°Ρ€Π°Π½Ρ‚ΠΈΡ€ΡƒΠ΅Ρ‚, Ρ‡Ρ‚ΠΎ сравнСниС Π±ΡƒΠ΄Π΅Ρ‚ ΠΊΠΎΡ€Ρ€Π΅ΠΊΡ‚Π½Ρ‹ΠΌ нСзависимо ΠΎΡ‚ Π΄ΠΈΠ°ΠΏΠ°Π·ΠΎΠ½Π° Π΄Π°Π½Π½Ρ‹Ρ….

Рассмотрим ΠΏΡ€ΠΈΠΌΠ΅Ρ€ Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ Π½Π° встроСнном языкС 1Π‘. ΠœΡ‹ создадим массив чисСл ΠΈ пройдСмся ΠΏΠΎ Π½Π΅ΠΌΡƒ Ρ†ΠΈΠΊΠ»ΠΎΠΌ Для КаТдого, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ являСтся Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ Ρ‡ΠΈΡ‚Π°Π΅ΠΌΡ‹ΠΌ конструктом Π² соврСмСнном ΠΊΠΎΠ΄Π΅ 1Π‘.

МассивЧисСл = Новый Массив;

МассивЧисСл.Π”ΠΎΠ±Π°Π²ΠΈΡ‚ΡŒ(15);

МассивЧисСл.Π”ΠΎΠ±Π°Π²ΠΈΡ‚ΡŒ(3);

МассивЧисСл.Π”ΠΎΠ±Π°Π²ΠΈΡ‚ΡŒ(42);

МассивЧисСл.Π”ΠΎΠ±Π°Π²ΠΈΡ‚ΡŒ(7);

Если МассивЧисСл.ΠšΠΎΠ»ΠΈΡ‡Π΅ΡΡ‚Π²ΠΎ() > 0 Π’ΠΎΠ³Π΄Π°

ΠœΠ°ΠΊΡΠΈΠΌΡƒΠΌ = МассивЧисСл[0];

Для КаТдого Число Из МассивЧисСл Π¦ΠΈΠΊΠ»

Если Число > ΠœΠ°ΠΊΡΠΈΠΌΡƒΠΌ Π’ΠΎΠ³Π΄Π°

ΠœΠ°ΠΊΡΠΈΠΌΡƒΠΌ = Число;

ΠšΠΎΠ½Π΅Ρ†Π•ΡΠ»ΠΈ;

ΠšΠΎΠ½Π΅Ρ†Π¦ΠΈΠΊΠ»Π°;

ΠšΠΎΠ½Π΅Ρ†Π•ΡΠ»ΠΈ;

Π’Π°ΠΊΠΎΠΉ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ обСспСчиваСт ΠΏΠΎΠ»Π½Ρ‹ΠΉ ΠΊΠΎΠ½Ρ‚Ρ€ΠΎΠ»ΡŒ Π½Π°Π΄ процСссом сравнСния. Π’Ρ‹ ΠΌΠΎΠΆΠ΅Ρ‚Π΅ Π»Π΅Π³ΠΊΠΎ Π΄ΠΎΠ±Π°Π²ΠΈΡ‚ΡŒ Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒΠ½ΡƒΡŽ Π»ΠΎΠ³ΠΈΠΊΡƒ, Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, поиск Π½Π΅ просто максимального значСния, Π° индСкса этого элСмСнта ΠΈΠ»ΠΈ всСх элСмСнтов, Ρ€Π°Π²Π½Ρ‹Ρ… максимуму. Π­Ρ‚ΠΎ Π΄Π΅Π»Π°Π΅Ρ‚ ΠΌΠ΅Ρ‚ΠΎΠ΄ Π³ΠΈΠ±ΠΊΠΈΠΌ инструмСнтом Π² арсСналС Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊΠ°.

πŸ’‘

ВсСгда провСряйтС массив Π½Π° пустоту ΠΏΠ΅Ρ€Π΅Π΄ Π½Π°Ρ‡Π°Π»ΠΎΠΌ Ρ†ΠΈΠΊΠ»Π°. ΠŸΠΎΠΏΡ‹Ρ‚ΠΊΠ° ΠΎΠ±Ρ€Π°Ρ‚ΠΈΡ‚ΡŒΡΡ ΠΊ элСмСнту ΠΏΠΎ индСксу [0] Π² пустом массивС Π²Ρ‹Π·ΠΎΠ²Π΅Ρ‚ ΠΈΡΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΠ΅ "ИндСкс Π·Π° ΠΏΡ€Π΅Π΄Π΅Π»Π°ΠΌΠΈ Π΄ΠΈΠ°ΠΏΠ°Π·ΠΎΠ½Π°".

ИспользованиС встроСнных Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ ΠΈ ΠΎΠ±ΡŠΠ΅ΠΊΡ‚ΠΎΠ² ΠΊΠΎΠ»Π»Π΅ΠΊΡ†ΠΈΠΈ

ΠŸΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΠ° 1Π‘ постоянно развиваСтся, ΠΈ Π² соврСмСнных вСрсиях появились Π±ΠΎΠ»Π΅Π΅ ΡƒΠ΄ΠΎΠ±Π½Ρ‹Π΅ инструмСнты для Ρ€Π°Π±ΠΎΡ‚Ρ‹ с Π΄Π°Π½Π½Ρ‹ΠΌΠΈ. Π’ частности, ΠΎΠ±ΡŠΠ΅ΠΊΡ‚ Массив сам ΠΏΠΎ сСбС Π½Π΅ ΠΈΠΌΠ΅Π΅Ρ‚ ΠΌΠ΅Ρ‚ΠΎΠ΄Π° .Макс(), ΠΊΠ°ΠΊ это Ρ€Π΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Π½ΠΎ Π² Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… Π΄Ρ€ΡƒΠ³ΠΈΡ… языках программирования. Однако, Ссли ваши Π΄Π°Π½Π½Ρ‹Π΅ прСдставлСны Π² Π²ΠΈΠ΄Π΅ ΠΎΠ±ΡŠΠ΅ΠΊΡ‚Π° Π’Π°Π±Π»ΠΈΡ†Π°Π—Π½Π°Ρ‡Π΅Π½ΠΈΠΉ ΠΈΠ»ΠΈ ΠšΠΎΠ»Π»Π΅ΠΊΡ†ΠΈΡΠ—Π½Π°Ρ‡Π΅Π½ΠΈΠΉ, Π·Π°Π΄Π°Ρ‡Π° упрощаСтся.

Для ΠΎΠ±ΡŠΠ΅ΠΊΡ‚Π° Π’Π°Π±Π»ΠΈΡ†Π°Π—Π½Π°Ρ‡Π΅Π½ΠΈΠΉ сущСствуСт ΠΌΠΎΡ‰Π½Ρ‹ΠΉ ΠΌΠ΅Ρ‚ΠΎΠ΄ Макс(), ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ позволяСт Π½Π°ΠΉΡ‚ΠΈ максимальноС Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Π² ΠΊΠΎΠ½ΠΊΡ€Π΅Ρ‚Π½ΠΎΠΉ ΠΊΠΎΠ»ΠΎΠ½ΠΊΠ΅. Π­Ρ‚ΠΎ особСнно ΡƒΠ΄ΠΎΠ±Π½ΠΎ, ΠΊΠΎΠ³Π΄Π° Π²Ρ‹ ΡƒΠΆΠ΅ Π·Π°Π³Ρ€ΡƒΠ·ΠΈΠ»ΠΈ Π΄Π°Π½Π½Ρ‹Π΅ ΠΈΠ· Π±Π°Π·Ρ‹ Π² Ρ‚Π°Π±Π»ΠΈΡ‡Π½ΡƒΡŽ Ρ‡Π°ΡΡ‚ΡŒ для дальнСйшСй ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ Π² памяти. ИспользованиС встроСнных ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠ² часто Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ быстрСС, Ρ‡Π΅ΠΌ Ρ€ΡƒΡ‡Π½Ρ‹Π΅ Ρ†ΠΈΠΊΠ»Ρ‹, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ ΠΎΠ½ΠΈ ΠΎΠΏΡ‚ΠΈΠΌΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Π½Ρ‹ Π½Π° ΡƒΡ€ΠΎΠ²Π½Π΅ ядра ΠΏΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΡ‹.

⚠️ Π’Π½ΠΈΠΌΠ°Π½ΠΈΠ΅: ΠœΠ΅Ρ‚ΠΎΠ΄ Макс() Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ чувствитСлСн ΠΊ Ρ‚ΠΈΠΏΡƒ Π΄Π°Π½Π½Ρ‹Ρ… Π² ΠΊΠΎΠ»ΠΎΠ½ΠΊΠ΅. Если Π² ΠΎΠ΄Π½ΠΎΠΉ ΠΊΠΎΠ»ΠΎΠ½ΠΊΠ΅ ΡΠΌΠ΅ΡˆΠ°Π½Ρ‹ числа ΠΈ строки, ΠΈΠ»ΠΈ Ссли ΠΊΠΎΠ»ΠΎΠ½ΠΊΠ° содСрТит Π½Π΅ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½Ρ‹Π΅ значСния (Null), ΠΌΠ΅Ρ‚ΠΎΠ΄ ΠΌΠΎΠΆΠ΅Ρ‚ Π²Π΅Ρ€Π½ΡƒΡ‚ΡŒ Π½Π΅ΠΎΠΆΠΈΠ΄Π°Π½Π½Ρ‹ΠΉ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ ΠΈΠ»ΠΈ Π²Ρ‹Π·Π²Π°Ρ‚ΡŒ ΠΎΡˆΠΈΠ±ΠΊΡƒ.

Если ΠΆΠ΅ Ρƒ вас ΠΈΠΌΠ΅Π½Π½ΠΎ массив, Π΅Π³ΠΎ ΠΌΠΎΠΆΠ½ΠΎ Π²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎ ΠΏΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΠΎΠ²Π°Ρ‚ΡŒ Π² Ρ‚Π°Π±Π»ΠΈΡ†Ρƒ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ для использования встроСнных Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ, хотя это ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ ΠΈΠ·Π±Ρ‹Ρ‚ΠΎΡ‡Π½Ρ‹ΠΌ с Ρ‚ΠΎΡ‡ΠΊΠΈ зрСния ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ для Π½Π΅Π±ΠΎΠ»ΡŒΡˆΠΈΡ… Π½Π°Π±ΠΎΡ€ΠΎΠ² Π΄Π°Π½Π½Ρ‹Ρ…. Π‘ΠΎΠ»Π΅Π΅ элСгантным Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ΠΌ для ΠΎΠ΄Π½ΠΎΡ€ΠΎΠ΄Π½Ρ‹Ρ… числовых массивов являСтся использованиС ΠΎΠ±ΡŠΠ΅ΠΊΡ‚Π° ΠšΠΎΠ»Π»Π΅ΠΊΡ†ΠΈΡΠ—Π½Π°Ρ‡Π΅Π½ΠΈΠΉ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Ρ‚Π°ΠΊΠΆΠ΅ ΠΏΠΎΠ΄Π΄Π΅Ρ€ΠΆΠΈΠ²Π°Π΅Ρ‚ ΠΌΠ΅Ρ‚ΠΎΠ΄Ρ‹ Π°Π³Ρ€Π΅Π³Π°Ρ†ΠΈΠΈ.

ΠŸΠΎΡ‡Π΅ΠΌΡƒ Ρƒ Массива Π½Π΅Ρ‚ ΠΌΠ΅Ρ‚ΠΎΠ΄Π° Макс?

АрхитСктура ΠΎΠ±ΡŠΠ΅ΠΊΡ‚Π° Массив Π² 1Π‘ ΠΎΡ€ΠΈΠ΅Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π° Π½Π° ΡƒΠ½ΠΈΠ²Π΅Ρ€ΡΠ°Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ хранСния Π»ΡŽΠ±Ρ‹Ρ… Ρ‚ΠΈΠΏΠΎΠ² Π΄Π°Π½Π½Ρ‹Ρ… Π²ΠΏΠ΅Ρ€Π΅ΠΌΠ΅ΡˆΠΊΡƒ. РСализация ΠΌΠ΅Ρ‚ΠΎΠ΄Π° сравнСния Ρ‚Ρ€Π΅Π±ΠΎΠ²Π°Π»Π° Π±Ρ‹ строгой Ρ‚ΠΈΠΏΠΈΠ·Π°Ρ†ΠΈΠΈ ΠΈΠ»ΠΈ слоТной Π»ΠΎΠ³ΠΈΠΊΠΈ привСдСния Ρ‚ΠΈΠΏΠΎΠ², Ρ‡Ρ‚ΠΎ Π·Π°ΠΌΠ΅Π΄Π»ΠΈΠ»ΠΎ Π±Ρ‹ Π±Π°Π·ΠΎΠ²Ρ‹Π΅ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ доступа ΠΏΠΎ индСксу.

ΠžΡΠΎΠ±Π΅Π½Π½ΠΎΡΡ‚ΠΈ сравнСния Ρ€Π°Π·Π½ΠΎΡ‚ΠΈΠΏΠ½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…

Одной ΠΈΠ· ΡƒΠ½ΠΈΠΊΠ°Π»ΡŒΠ½Ρ‹Ρ… особСнностСй языка 1Π‘ являСтся Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ хранСния Π² ΠΎΠ΄Π½ΠΎΠΌ массивС Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ Ρ€Π°Π·Π½Ρ‹Ρ… Ρ‚ΠΈΠΏΠΎΠ². Π’Ρ‹ ΠΌΠΎΠΆΠ΅Ρ‚Π΅ ΠΏΠΎΠ»ΠΎΠΆΠΈΡ‚ΡŒ Π² ΠΎΠ΄Π½Ρƒ структуру число, Π΄Π°Ρ‚Ρƒ, строку ΠΈ Π΄Π°ΠΆΠ΅ ссылку Π½Π° Π΄ΠΎΠΊΡƒΠΌΠ΅Π½Ρ‚. Однако поиск максимального элСмСнта Π² Ρ‚Π°ΠΊΠΎΠΌ "Π²ΠΈΠ½Π΅Π³Ρ€Π΅Ρ‚Π΅" прСдставляСт собой Π½Π΅Ρ‚Ρ€ΠΈΠ²ΠΈΠ°Π»ΡŒΠ½ΡƒΡŽ Π·Π°Π΄Π°Ρ‡Ρƒ, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ ΠΏΡ€Π°Π²ΠΈΠ»Π° сравнСния Ρ€Π°Π·Π½ΠΎΡ‚ΠΈΠΏΠ½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… строго Ρ€Π΅Π³Π»Π°ΠΌΠ΅Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Ρ‹.

Π’ 1Π‘ сущСствуСт иСрархия Ρ‚ΠΈΠΏΠΎΠ² Π΄Π°Π½Π½Ρ‹Ρ…. ΠŸΡ€ΠΈ сравнСнии Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ Ρ€Π°Π·Π½Ρ‹Ρ… Ρ‚ΠΈΠΏΠΎΠ² систСма руководствуСтся Π²Π½ΡƒΡ‚Ρ€Π΅Π½Π½ΠΈΠΌΠΈ ΠΏΡ€Π°Π²ΠΈΠ»Π°ΠΌΠΈ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚Π°. НапримСр, число всСгда мСньшС, Ρ‡Π΅ΠΌ строка, Π° строка мСньшС, Ρ‡Π΅ΠΌ Π΄Π°Ρ‚Π°. ПониманиС этой ΠΈΠ΅Ρ€Π°Ρ€Ρ…ΠΈΠΈ критичСски Π²Π°ΠΆΠ½ΠΎ, Ссли Π²Ρ‹ Π½Π΅ Π³Π°Ρ€Π°Π½Ρ‚ΠΈΡ€ΡƒΠ΅Ρ‚Π΅ ΠΎΠ΄Π½ΠΎΡ€ΠΎΠ΄Π½ΠΎΡΡ‚ΡŒ Π΄Π°Π½Π½Ρ‹Ρ… Π² своСм массивС.

НиТС ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Π° упрощСнная Ρ‚Π°Π±Π»ΠΈΡ†Π° ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚ΠΎΠ² Ρ‚ΠΈΠΏΠΎΠ² Π΄Π°Π½Π½Ρ‹Ρ… ΠΏΡ€ΠΈ сравнСнии Π² 1Π‘:

Π’ΠΈΠΏ Π΄Π°Π½Π½Ρ‹Ρ… ΠŸΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚ (ΠΎΡ‚ мСньшСго ΠΊ Π±ΠΎΠ»ΡŒΡˆΠ΅ΠΌΡƒ) ΠŸΡ€ΠΈΠΌΠ΅Ρ€ значСния
НСопрСдСлСно 1 (Π‘Π°ΠΌΡ‹ΠΉ Π½ΠΈΠ·ΠΊΠΈΠΉ) НСопрСдСлСно
Число 2 100.50
Π‘Ρ‚Ρ€ΠΎΠΊΠ° 3 "ВСкст"
Π”Π°Ρ‚Π° 4 2023-10-01
Π‘ΡƒΠ»Π΅Π²ΠΎ 5 Π˜ΡΡ‚ΠΈΠ½Π°

Если ваш Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ наткнСтся Π½Π° ΡΠΌΠ΅ΡˆΠ°Π½Π½Ρ‹Π΅ Ρ‚ΠΈΠΏΡ‹, Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ сравнСния ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ логичСски Π²Π΅Ρ€Π½Ρ‹ΠΌ с Ρ‚ΠΎΡ‡ΠΊΠΈ зрСния Π΄Π²ΠΈΠΆΠΊΠ° 1Π‘, Π½ΠΎ бСссмыслСнным для бизнСса. НапримСр, Π΄Π°Ρ‚Π° "01.01.2000" Π±ΡƒΠ΄Π΅Ρ‚ ΡΡ‡ΠΈΡ‚Π°Ρ‚ΡŒΡΡ "большС", Ρ‡Π΅ΠΌ число 999999. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ ΠΏΠ΅Ρ€Π΅Π΄ поиском максимума Π½Π°ΡΡ‚ΠΎΡΡ‚Π΅Π»ΡŒΠ½ΠΎ рСкомСндуСтся Π²Ρ‹ΠΏΠΎΠ»Π½ΡΡ‚ΡŒ Ρ„ΠΈΠ»ΡŒΡ‚Ρ€Π°Ρ†ΠΈΡŽ ΠΈΠ»ΠΈ ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½ΠΈΠ΅ Ρ‚ΠΈΠΏΠΎΠ².

πŸ“Š Π‘ ΠΊΠ°ΠΊΠΈΠΌ Ρ‚ΠΈΠΏΠΎΠΌ Π΄Π°Π½Π½Ρ‹Ρ… Π²Ρ‹ Ρ‡Π°Ρ‰Π΅ всСго Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚Π΅ Π² массивах?
Числа (суммы, количСства)
Π”Π°Ρ‚Ρ‹ (ΠΏΠ΅Ρ€ΠΈΠΎΠ΄Ρ‹ ΠΎΡ‚Ρ‡Π΅Ρ‚ΠΎΠ²)
Π‘Ρ‚Ρ€ΠΎΠΊΠΈ (наимСнования)
Бсылки Π½Π° ΠΎΠ±ΡŠΠ΅ΠΊΡ‚Ρ‹ Π˜Π‘
Π‘ΠΌΠ΅ΡˆΠ°Π½Π½Ρ‹Π΅ Ρ‚ΠΈΠΏΡ‹

Поиск максимума Π² массивС структур ΠΈ ΠΎΠ±ΡŠΠ΅ΠΊΡ‚ΠΎΠ²

На ΠΏΡ€Π°ΠΊΡ‚ΠΈΠΊΠ΅ Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊΠΈ Ρ€Π΅Π΄ΠΊΠΎ хранят Π² массивах ΠΏΡ€ΠΈΠΌΠΈΡ‚ΠΈΠ²Π½Ρ‹Π΅ Ρ‚ΠΈΠΏΡ‹ Π΄Π°Π½Π½Ρ‹Ρ…. Π§Π°Ρ‰Π΅ всСго массив состоит ΠΈΠ· ΠΎΠ±ΡŠΠ΅ΠΊΡ‚ΠΎΠ² Ρ‚ΠΈΠΏΠ° Π‘Ρ‚Ρ€ΡƒΠΊΡ‚ΡƒΡ€Π° ΠΈΠ»ΠΈ ΠžΠ±ΡŠΠ΅ΠΊΡ‚ΠœΠ΅Ρ‚ΠΎΠ΄Π°Π½Π½Ρ‹Ρ…. Π’ Ρ‚Π°ΠΊΠΈΡ… случаях Π·Π°Π΄Π°Ρ‡Π° трансформируСтся: Π½Π°ΠΌ Π½ΡƒΠΆΠ½ΠΎ Π½Π°ΠΉΡ‚ΠΈ Π½Π΅ просто максимальноС Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅, Π° элСмСнт массива (структуру), Ρƒ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½ΠΎΠ΅ ΠΏΠΎΠ»Π΅ ΠΈΠΌΠ΅Π΅Ρ‚ максимальноС Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅.

Алгоритм услоТняСтся Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎΡΡ‚ΡŒΡŽ доступа ΠΊ свойствам Π²Π»ΠΎΠΆΠ΅Π½Π½Ρ‹Ρ… ΠΎΠ±ΡŠΠ΅ΠΊΡ‚ΠΎΠ². Π’Π°ΠΌ потрСбуСтся ΠΈΠ·Π²Π»Π΅ΠΊΠ°Ρ‚ΡŒ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ ΠΏΠΎ ΠΊΠ»ΡŽΡ‡Ρƒ Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΈ Ρ†ΠΈΠΊΠ»Π°. Π­Ρ‚ΠΎ создаСт Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒΠ½ΡƒΡŽ Π½Π°Π³Ρ€ΡƒΠ·ΠΊΡƒ Π½Π° ΠΈΠ½Ρ‚Π΅Ρ€ΠΏΡ€Π΅Ρ‚Π°Ρ‚ΠΎΡ€, поэтому оптимизация ΠΊΠΎΠ΄Π° становится Π²Π°ΠΆΠ½ΠΎΠΉ. Π˜Π·Π±Π΅Π³Π°ΠΉΡ‚Π΅ Π»ΠΈΡˆΠ½ΠΈΡ… Π²Ρ‹Π·ΠΎΠ²ΠΎΠ² Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ Π²Π½ΡƒΡ‚Ρ€ΠΈ Ρ†ΠΈΠΊΠ»Π° сравнСния.

Рассмотрим ΠΏΡ€ΠΈΠΌΠ΅Ρ€ поиска структуры с максимальной суммой ΠΏΡ€ΠΎΠ΄Π°ΠΆΠΈ:

ΠœΠ°ΡΡΠΈΠ²ΠŸΡ€ΠΎΠ΄Π°ΠΆ = Новый Массив;

// Π—Π°ΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ массива структурами

Π‘Ρ‚Ρ€1 = Новый Π‘Ρ‚Ρ€ΡƒΠΊΡ‚ΡƒΡ€Π°("Π’ΠΎΠ²Π°Ρ€, Π‘ΡƒΠΌΠΌΠ°", "Π’ΠΎΠ²Π°Ρ€1", 100);

Π‘Ρ‚Ρ€2 = Новый Π‘Ρ‚Ρ€ΡƒΠΊΡ‚ΡƒΡ€Π°("Π’ΠΎΠ²Π°Ρ€, Π‘ΡƒΠΌΠΌΠ°", "Π’ΠΎΠ²Π°Ρ€2", 500);

ΠœΠ°ΡΡΠΈΠ²ΠŸΡ€ΠΎΠ΄Π°ΠΆ.Π”ΠΎΠ±Π°Π²ΠΈΡ‚ΡŒ(Π‘Ρ‚Ρ€1);

ΠœΠ°ΡΡΠΈΠ²ΠŸΡ€ΠΎΠ΄Π°ΠΆ.Π”ΠΎΠ±Π°Π²ΠΈΡ‚ΡŒ(Π‘Ρ‚Ρ€2);

ΠœΠ°ΠΊΡΠ‘Ρ‚Ρ€ΡƒΠΊΡ‚ΡƒΡ€Π° = НСопрСдСлСно;

ΠœΠ°ΠΊΡΠ‘ΡƒΠΌΠΌΠ° = -1;

Для КаТдого Π­Π»Π΅ΠΌΠ΅Π½Ρ‚ Из ΠœΠ°ΡΡΠΈΠ²ΠŸΡ€ΠΎΠ΄Π°ΠΆ Π¦ΠΈΠΊΠ»

ВСкущаяБумма = Π­Π»Π΅ΠΌΠ΅Π½Ρ‚.Π‘ΡƒΠΌΠΌΠ°;

Если ВСкущаяБумма > ΠœΠ°ΠΊΡΠ‘ΡƒΠΌΠΌΠ° Π’ΠΎΠ³Π΄Π°

ΠœΠ°ΠΊΡΠ‘ΡƒΠΌΠΌΠ° = ВСкущаяБумма;

ΠœΠ°ΠΊΡΠ‘Ρ‚Ρ€ΡƒΠΊΡ‚ΡƒΡ€Π° = Π­Π»Π΅ΠΌΠ΅Π½Ρ‚;

ΠšΠΎΠ½Π΅Ρ†Π•ΡΠ»ΠΈ;

ΠšΠΎΠ½Π΅Ρ†Π¦ΠΈΠΊΠ»Π°;

ΠžΠ±Ρ€Π°Ρ‚ΠΈΡ‚Π΅ Π²Π½ΠΈΠΌΠ°Π½ΠΈΠ΅, Ρ‡Ρ‚ΠΎ ΠΌΡ‹ сохраняСм ссылку Π½Π° саму структуру ΠœΠ°ΠΊΡΠ‘Ρ‚Ρ€ΡƒΠΊΡ‚ΡƒΡ€Π°, Π° Π½Π΅ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π½Π° Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ суммы. Π­Ρ‚ΠΎ позволяСт Π² дальнСйшСм ΠΎΠ±Ρ€Π°Ρ‚ΠΈΡ‚ΡŒΡΡ ΠΊ Π΄Ρ€ΡƒΠ³ΠΈΠΌ полям Π½Π°ΠΉΠ΄Π΅Π½Π½ΠΎΠ³ΠΎ элСмСнта, Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, ΡƒΠ·Π½Π°Ρ‚ΡŒ Π½Π°ΠΈΠΌΠ΅Π½ΠΎΠ²Π°Π½ΠΈΠ΅ Ρ‚ΠΎΠ²Π°Ρ€Π°-Π»ΠΈΠ΄Π΅Ρ€Π° ΠΏΡ€ΠΎΠ΄Π°ΠΆ. Π’Π°ΠΊΠΎΠΉ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ являСтся стандартом Π΄Π΅-Ρ„Π°ΠΊΡ‚ΠΎ ΠΏΡ€ΠΈ Ρ€Π°Π±ΠΎΡ‚Π΅ с коллСкциями ΠΎΠ±ΡŠΠ΅ΠΊΡ‚ΠΎΠ² Π² 1Π‘.

⚠️ Π’Π½ΠΈΠΌΠ°Π½ΠΈΠ΅: ΠŸΡ€ΠΈ сравнСнии ΠΏΠΎΠ»Π΅ΠΉ структур ΡƒΠ±Π΅Π΄ΠΈΡ‚Π΅ΡΡŒ, Ρ‡Ρ‚ΠΎ ΠΊΠ»ΡŽΡ‡ сущСствуСт Π²ΠΎ всСх элСмСнтах массива. ΠŸΠΎΠΏΡ‹Ρ‚ΠΊΠ° ΠΎΠ±Ρ€Π°Ρ‚ΠΈΡ‚ΡŒΡΡ ΠΊ Π½Π΅ΡΡƒΡ‰Π΅ΡΡ‚Π²ΡƒΡŽΡ‰Π΅ΠΌΡƒ ΠΊΠ»ΡŽΡ‡Ρƒ структуры Π²Π΅Ρ€Π½Π΅Ρ‚ НСопрСдСлСно, Ρ‡Ρ‚ΠΎ ΠΌΠΎΠΆΠ΅Ρ‚ Π½Π°Ρ€ΡƒΡˆΠΈΡ‚ΡŒ Π»ΠΎΠ³ΠΈΠΊΡƒ сравнСния чисСл.

ΠŸΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ ΠΈ оптимизация Π±ΠΎΠ»ΡŒΡˆΠΈΡ… массивов

Когда объСм Π΄Π°Π½Π½Ρ‹Ρ… исчисляСтся дСсятками ΠΈΠ»ΠΈ сотнями тысяч строк, вопрос ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ Π²Ρ‹Ρ…ΠΎΠ΄ΠΈΡ‚ Π½Π° ΠΏΠ΅Ρ€Π²Ρ‹ΠΉ ΠΏΠ»Π°Π½. Наивная рСализация Ρ†ΠΈΠΊΠ»Π° ΠΌΠΎΠΆΠ΅Ρ‚ ΡΡ‚Π°Ρ‚ΡŒ "ΡƒΠ·ΠΊΠΈΠΌ Π³ΠΎΡ€Π»Ρ‹ΡˆΠΊΠΎΠΌ" Π² высоконагруТСнных систСмах, особСнно Ссли поиск максимума выполняСтся Π²Π½ΡƒΡ‚Ρ€ΠΈ Π²Π»ΠΎΠΆΠ΅Π½Π½Ρ‹Ρ… Ρ†ΠΈΠΊΠ»ΠΎΠ² ΠΈΠ»ΠΈ рСгистров накоплСния.

ΠŸΠ΅Ρ€Π²ΠΎΠ΅ ΠΏΡ€Π°Π²ΠΈΠ»ΠΎ ΠΎΠΏΡ‚ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ β€” минимизация ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΉ Π²Π½ΡƒΡ‚Ρ€ΠΈ Ρ†ΠΈΠΊΠ»Π°. Π›ΡŽΠ±Ρ‹Π΅ вычислСния, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π½Π΅ зависят ΠΎΡ‚ Ρ‚Π΅ΠΊΡƒΡ‰Π΅ΠΉ ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΈ, Π΄ΠΎΠ»ΠΆΠ½Ρ‹ Π±Ρ‹Ρ‚ΡŒ вынСсСны Π·Π° ΠΏΡ€Π΅Π΄Π΅Π»Ρ‹ Ρ†ΠΈΠΊΠ»Π°. Π’Π°ΠΊΠΆΠ΅ слСдуСт ΠΈΠ·Π±Π΅Π³Π°Ρ‚ΡŒ создания Π½ΠΎΠ²Ρ‹Ρ… ΠΎΠ±ΡŠΠ΅ΠΊΡ‚ΠΎΠ² Π²Π½ΡƒΡ‚Ρ€ΠΈ Ρ‚Π΅Π»Π° Ρ†ΠΈΠΊΠ»Π°. Если Π²Ρ‹ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚Π΅ Π²Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅ для хранСния Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ΠΎΠ² ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠ², ΠΎΠ±ΡŠΡΠ²Π»ΡΠΉΡ‚Π΅ ΠΈΡ… Π·Π°Ρ€Π°Π½Π΅Π΅.

Π’Ρ‚ΠΎΡ€ΠΎΠΉ аспСкт β€” Π²Ρ‹Π±ΠΎΡ€ структуры Π΄Π°Π½Π½Ρ‹Ρ…. Если Π²Π°ΠΌ Π½ΡƒΠΆΠ½ΠΎ часто ΠΈΡΠΊΠ°Ρ‚ΡŒ максимум, Π΄ΠΎΠ±Π°Π²Π»ΡΡ‚ΡŒ ΠΈ ΡƒΠ΄Π°Π»ΡΡ‚ΡŒ элСмСнты, рассмотритС использованиС Π”Π΅Ρ€Π΅Π²ΠΎΠ—Π½Π°Ρ‡Π΅Π½ΠΈΠΉ ΠΈΠ»ΠΈ сортированного Массива. Π’ отсортированном массивС поиск максимума сводится ΠΊ ΠΎΠ±Ρ€Π°Ρ‰Π΅Π½ΠΈΡŽ ΠΊ послСднСму элСмСнту, Ρ‡Ρ‚ΠΎ являСтся ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠ΅ΠΉ константной слоТности O(1), Π² ΠΎΡ‚Π»ΠΈΡ‡ΠΈΠ΅ ΠΎΡ‚ Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ³ΠΎ ΠΏΠ΅Ρ€Π΅Π±ΠΎΡ€Π° O(N).

β˜‘οΈ ΠžΠΏΡ‚ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΡ Ρ†ΠΈΠΊΠ»Π° поиска

Π’Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ΠΎ: 0 / 4

Π‘Ρ‚ΠΎΠΈΡ‚ Ρ‚Π°ΠΊΠΆΠ΅ ΡƒΠΏΠΎΠΌΡΠ½ΡƒΡ‚ΡŒ ΠΎ многопоточности. Π’ соврСмСнных вСрсиях ΠΏΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΡ‹ 1Π‘ (начиная с 8.3.Ρ…Ρ…) ΡΡƒΡ‰Π΅ΡΡ‚Π²ΡƒΡŽΡ‚ ΠΌΠ΅Ρ…Π°Π½ΠΈΠ·ΠΌΡ‹ ΠΏΠ°Ρ€Π°Π»Π»Π΅Π»ΡŒΠ½ΠΎΠ³ΠΎ выполнСния ΠΊΠΎΠ΄Π°. Для ΠΎΠ³Ρ€ΠΎΠΌΠ½Ρ‹Ρ… массивов ΠΌΠΎΠΆΠ½ΠΎ Ρ€Π΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Ρ‚ΡŒ Ρ€Π°Π·Π΄Π΅Π»Π΅Π½ΠΈΠ΅ Π΄Π°Π½Π½Ρ‹Ρ… Π½Π° части ΠΈ поиск Π»ΠΎΠΊΠ°Π»ΡŒΠ½Ρ‹Ρ… максимумов Π² ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΠΏΠΎΡ‚ΠΎΠΊΠ΅ с ΠΏΠΎΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΌ сравнСниСм Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ΠΎΠ². Однако для стандартных Π·Π°Π΄Π°Ρ‡ бизнСса это часто ΠΈΠ·Π±Ρ‹Ρ‚ΠΎΡ‡Π½ΠΎ ΠΈ услоТняСт ΠΏΠΎΠ΄Π΄Π΅Ρ€ΠΆΠΊΡƒ ΠΊΠΎΠ΄Π°.

ΠžΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ° ошибок ΠΈ Π³Ρ€Π°Π½ΠΈΡ‡Π½Ρ‹Π΅ случаи

НадСТный ΠΊΠΎΠ΄ Π΄ΠΎΠ»ΠΆΠ΅Π½ ΠΏΡ€Π΅Π΄Π²ΠΈΠ΄Π΅Ρ‚ΡŒ Π½Π΅ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΡˆΡ‚Π°Ρ‚Π½Ρ‹Π΅ ситуации, Π½ΠΎ ΠΈ ΠΈΡΠΊΠ»ΡŽΡ‡ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹Π΅ сцСнарии. Π§Ρ‚ΠΎ Π΄ΠΎΠ»ΠΆΠ΅Π½ ΡΠ΄Π΅Π»Π°Ρ‚ΡŒ ваш Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ, Ссли массив пуст? А Ссли всС элСмСнты Ρ€Π°Π²Π½Ρ‹ Null? Или Ссли Π² массивС чисСл Π·Π°Ρ‚Π΅ΡΠ°Π»Π°ΡΡŒ строка "Ошибка"? Π˜Π³Π½ΠΎΡ€ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ этих случаСв ΠΌΠΎΠΆΠ΅Ρ‚ привСсти ΠΊ падСнию клиСнтского прилоТСния ΠΈΠ»ΠΈ Ρ„ΠΎΡ€ΠΌΠΈΡ€ΠΎΠ²Π°Π½ΠΈΡŽ Π½Π΅ΠΊΠΎΡ€Ρ€Π΅ΠΊΡ‚Π½Ρ‹Ρ… ΠΎΡ‚Ρ‡Π΅Ρ‚ΠΎΠ².

РСкомСндуСтся всСгда явно ΠΎΠ±Ρ€Π°Π±Π°Ρ‚Ρ‹Π²Π°Ρ‚ΡŒ случай пустого массива. ВмСсто Ρ‚ΠΎΠ³ΠΎ Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡ‚ΡŒ ΠΊΠΎΠ΄Ρƒ ΡƒΠΏΠ°ΡΡ‚ΡŒ с ошибкой, Π»ΡƒΡ‡ΡˆΠ΅ Π²Π΅Ρ€Π½ΡƒΡ‚ΡŒ ΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎΠ΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ (Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, НСопрСдСлСно ΠΈΠ»ΠΈ 0), ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ Π²Ρ‹Π·Ρ‹Π²Π°ΡŽΡ‰Π°Ρ функция смоТСт ΠΊΠΎΡ€Ρ€Π΅ΠΊΡ‚Π½ΠΎ ΠΈΠ½Ρ‚Π΅Ρ€ΠΏΡ€Π΅Ρ‚ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ. Π­Ρ‚ΠΎ Π΄Π΅Π»Π°Π΅Ρ‚ ΠΏΠΎΠ²Π΅Π΄Π΅Π½ΠΈΠ΅ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ прСдсказуСмым.

Π’Π°ΠΊΠΆΠ΅ стоит ΠΏΡ€Π΅Π΄ΡƒΡΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Π»ΠΎΠ³ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ Π°Π½ΠΎΠΌΠ°Π»ΠΈΠΉ. Если Π²Ρ‹ ΠΎΠ±Π½Π°Ρ€ΡƒΠΆΠΈΠ»ΠΈ Π² числовом массивС Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ нСчислового Ρ‚ΠΈΠΏΠ°, Π·Π°ΠΏΠΈΡˆΠΈΡ‚Π΅ эту ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΡŽ Π² ΠΆΡƒΡ€Π½Π°Π» рСгистрации. Π­Ρ‚ΠΎ ΠΏΠΎΠΌΠΎΠΆΠ΅Ρ‚ Π² Π±ΡƒΠ΄ΡƒΡ‰Π΅ΠΌ Π²Ρ‹ΡΠ²ΠΈΡ‚ΡŒ ошибки Π² Π»ΠΎΠ³ΠΈΠΊΠ΅ формирования массива Π½Π° Π±ΠΎΠ»Π΅Π΅ Ρ€Π°Π½Π½ΠΈΡ… этапах.

πŸ’‘

ВсСгда Π²ΠΎΠ·Π²Ρ€Π°Ρ‰Π°ΠΉΡ‚Π΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Ρ‚ΠΎΠ³ΠΎ ΠΆΠ΅ Ρ‚ΠΈΠΏΠ°, Ρ‡Ρ‚ΠΎ оТидаСтся ΠΎΡ‚ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ. Если функция Π΄ΠΎΠ»ΠΆΠ½Π° Π²Π΅Ρ€Π½ΡƒΡ‚ΡŒ Число, Π½Π΅ Π²ΠΎΠ·Π²Ρ€Π°Ρ‰Π°ΠΉΡ‚Π΅ НСопрСдСлСно, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠΉΡ‚Π΅ 0 ΠΈΠ»ΠΈ ΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎΠ΅ константноС Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅, согласованноС с Π·Π°ΠΊΠ°Π·Ρ‡ΠΈΠΊΠΎΠΌ.

⚠️ Π’Π½ΠΈΠΌΠ°Π½ΠΈΠ΅: Π˜Π½Ρ‚Π΅Ρ€Ρ„Π΅ΠΉΡΡ‹ ΠΈ ΠΌΠ΅Ρ‚ΠΎΠ΄Ρ‹ Ρ€Π°Π±ΠΎΡ‚Ρ‹ с коллСкциями ΠΌΠΎΠ³ΡƒΡ‚ Π½Π΅Π·Π½Π°Ρ‡ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ ΠΎΡ‚Π»ΠΈΡ‡Π°Ρ‚ΡŒΡΡ Π² Ρ€Π°Π·Π½Ρ‹Ρ… конфигурациях (БухгалтСрия, Π—Π£ΠŸ, Π£Π’) ΠΈ вСрсиях ΠΏΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΡ‹. ВсСгда провСряйтС Π΄ΠΎΠΊΡƒΠΌΠ΅Π½Ρ‚Π°Ρ†ΠΈΡŽ ΠΊ ΠΊΠΎΠ½ΠΊΡ€Π΅Ρ‚Π½ΠΎΠΉ вСрсии API, Ссли ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚Π΅ Ρ€Π°ΡΡˆΠΈΡ€Π΅Π½Π½Ρ‹Π΅ возмоТности Ρ€Π°ΡΡˆΠΈΡ€Π΅Π½ΠΈΠΉ.

Часто Π·Π°Π΄Π°Π²Π°Π΅ΠΌΡ‹Π΅ вопросы (FAQ)

МоТно Π»ΠΈ Π½Π°ΠΉΡ‚ΠΈ максимум Π² массивС ΠΎΠ΄Π½ΠΎΠΉ строкой ΠΊΠΎΠ΄Π°?

Π’ чистом встроСнном языкС 1Π‘ для ΠΎΠ±ΡŠΠ΅ΠΊΡ‚Π° Массив Ρ‚Π°ΠΊΠΎΠΉ возмоТности Π½Π΅Ρ‚. Однако, Ссли ΠΏΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΠΎΠ²Π°Ρ‚ΡŒ массив Π² Π’Π°Π±Π»ΠΈΡ†ΡƒΠ—Π½Π°Ρ‡Π΅Π½ΠΈΠΉ, ΠΌΠΎΠΆΠ½ΠΎ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ ΠΌΠ΅Ρ‚ΠΎΠ΄ Π’Π°Π±Π»ΠΈΡ†Π°.Макс("ИмяКолонки"). Π­Ρ‚ΠΎ Π±ΡƒΠ΄Π΅Ρ‚ Π²Ρ‹Π³Π»ΡΠ΄Π΅Ρ‚ΡŒ ΠΊΠ°ΠΊ ΠΎΠ΄Π½Π° строка, Π½ΠΎ ΠΏΠΎΡ‚Ρ€Π΅Π±ΡƒΠ΅Ρ‚ Π½Π°ΠΊΠ»Π°Π΄Π½Ρ‹Ρ… расходов Π½Π° ΠΊΠΎΠ½Π²Π΅Ρ€Ρ‚Π°Ρ†ΠΈΡŽ Ρ‚ΠΈΠΏΠΎΠ² Π΄Π°Π½Π½Ρ‹Ρ….

Π§Ρ‚ΠΎ быстрСС: Ρ†ΠΈΠΊΠ» "Для" ΠΏΠΎ индСксу ΠΈΠ»ΠΈ "Для КаТдого"?

Π’ соврСмСнных вСрсиях ΠΏΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΡ‹ 1Π‘ Ρ€Π°Π·Π½ΠΈΡ†Π° Π² ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ ΠΌΠ΅ΠΆΠ΄Ρƒ Ρ†ΠΈΠΊΠ»ΠΎΠΌ Для i = 0 По ... ΠΈ Для КаТдого ... Из минимальна ΠΈ часто находится Π² ΠΏΡ€Π΅Π΄Π΅Π»Π°Ρ… ΠΏΠΎΠ³Ρ€Π΅ΡˆΠ½ΠΎΡΡ‚ΠΈ. Π¦ΠΈΠΊΠ» Для КаТдого ΠΏΡ€Π΅Π΄ΠΏΠΎΡ‡Ρ‚ΠΈΡ‚Π΅Π»ΡŒΠ½Π΅Π΅ с Ρ‚ΠΎΡ‡ΠΊΠΈ зрСния читаСмости ΠΊΠΎΠ΄Π° ΠΈ бСзопасности (Π·Π°Ρ‰ΠΈΡ‚Π° ΠΎΡ‚ Π²Ρ‹Ρ…ΠΎΠ΄Π° Π·Π° Π³Ρ€Π°Π½ΠΈΡ†Ρ‹ массива).

Как Π½Π°ΠΉΡ‚ΠΈ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡŒΠ½ΡƒΡŽ Π΄Π°Ρ‚Ρƒ Π² массивС?

Алгоритм ΠΏΠΎΠ»Π½ΠΎΡΡ‚ΡŒΡŽ Π°Π½Π°Π»ΠΎΠ³ΠΈΡ‡Π΅Π½ поиску максимального числа. Π”Π°Ρ‚Ρ‹ Π² 1Π‘ ΡΡ€Π°Π²Π½ΠΈΠ²Π°ΡŽΡ‚ΡΡ ΠΊΠΎΡ€Ρ€Π΅ΠΊΡ‚Π½ΠΎ. ЕдинствСнноС условиС β€” ΡƒΠ±Π΅Π΄ΠΈΡ‚Π΅ΡΡŒ, Ρ‡Ρ‚ΠΎ Π² массивС Π½Π΅Ρ‚ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ НСопрСдСлСно ΠΈΠ»ΠΈ пустых Π΄Π°Ρ‚, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ ΠΎΠ½ΠΈ ΠΌΠΎΠ³ΡƒΡ‚ ΠΈΡΠΊΠ°Π·ΠΈΡ‚ΡŒ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ сравнСния Π² зависимости ΠΎΡ‚ вСрсии ΠΏΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΡ‹.

Π§Ρ‚ΠΎ Π΄Π΅Π»Π°Ρ‚ΡŒ, Ссли Π² массивС нСсколько элСмСнтов с ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹ΠΌ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ΠΌ?

ΠšΠ»Π°ΡΡΠΈΡ‡Π΅ΡΠΊΠΈΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Π²Π΅Ρ€Π½Π΅Ρ‚ ΠΏΠ΅Ρ€Π²Ρ‹ΠΉ Π½Π°ΠΉΠ΄Π΅Π½Π½Ρ‹ΠΉ максимум. Если Π²Π°ΠΌ Π½ΡƒΠΆΠ½Ρ‹ всС Ρ‚Π°ΠΊΠΈΠ΅ элСмСнты, Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ Π²Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π΄Π²Π° ΠΏΡ€ΠΎΡ…ΠΎΠ΄Π°: ΠΏΠ΅Ρ€Π²Ρ‹ΠΉ для нахоТдСния значСния максимума, Π²Ρ‚ΠΎΡ€ΠΎΠΉ β€” для сбора всСх элСмСнтов, Ρ€Π°Π²Π½Ρ‹Ρ… этому Π·Π½Π°Ρ‡Π΅Π½ΠΈΡŽ, Π² Π½ΠΎΠ²Ρ‹ΠΉ массив ΠΈΠ»ΠΈ список.