Π Π°Π±ΠΎΡ‚Π° с коллСкциями Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ являСтся Π½Π΅ΠΎΡ‚ΡŠΠ΅ΠΌΠ»Π΅ΠΌΠΎΠΉ Ρ‡Π°ΡΡ‚ΡŒΡŽ Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ ΠΊΠΎΠ½Ρ„ΠΈΠ³ΡƒΡ€Π°Ρ†ΠΈΠΉ Π½Π° ΠΏΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΠ΅ 1Π‘:ΠŸΡ€Π΅Π΄ΠΏΡ€ΠΈΡΡ‚ΠΈΠ΅ 8. Часто ΠΏΠ΅Ρ€Π΅Π΄ программистом встаСт Π·Π°Π΄Π°Ρ‡Π° Π½Π΅ просто ΠΏΠ΅Ρ€Π΅Π±Ρ€Π°Ρ‚ΡŒ Π΄Π°Π½Π½Ρ‹Π΅, Π° Π½Π°ΠΉΡ‚ΠΈ ΠΊΠΎΠ½ΠΊΡ€Π΅Ρ‚Π½ΠΎΠ΅ ΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ элСмСнта Π²Π½ΡƒΡ‚Ρ€ΠΈ структуры. ПониманиС Ρ‚ΠΎΠ³ΠΎ, ΠΊΠ°ΠΊ Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ индСксация, критичСски Π²Π°ΠΆΠ½ΠΎ для ΠΎΠΏΡ‚ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ ΠΊΠΎΠ΄Π° ΠΈ прСдотвращСния ошибок Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ выполнСния.

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

ΠΠ°Ρ‡ΠΈΠ½Π°ΡŽΡ‰ΠΈΠ΅ Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊΠΈ часто ΠΏΡƒΡ‚Π°ΡŽΡ‚ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ элСмСнта ΠΈ Π΅Π³ΠΎ порядковый Π½ΠΎΠΌΠ΅Ρ€. Π­Ρ‚ΠΎ Ρ„ΡƒΠ½Π΄Π°ΠΌΠ΅Π½Ρ‚Π°Π»ΡŒΠ½ΠΎΠ΅ ΠΏΡ€Π°Π²ΠΈΠ»ΠΎ, Π½Π°Ρ€ΡƒΡˆΠ΅Π½ΠΈΠ΅ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ ΠΏΡ€ΠΈΠ²ΠΎΠ΄ΠΈΡ‚ ΠΊ ошибкС "ИндСкс значСния Π²Ρ‹Ρ…ΠΎΠ΄ΠΈΡ‚ Π·Π° ΠΏΡ€Π΅Π΄Π΅Π»Ρ‹ Π΄ΠΈΠ°ΠΏΠ°Π·ΠΎΠ½Π°".

Π‘Π°Π·ΠΎΠ²Ρ‹Π΅ ΠΏΡ€ΠΈΠ½Ρ†ΠΈΠΏΡ‹ индСксации Π² массивах 1Π‘

Массив Π² Ρ‚Π΅Ρ€ΠΌΠΈΠ½ΠΎΠ»ΠΎΠ³ΠΈΠΈ ΠΏΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΡ‹ 1Π‘ β€” это упорядочСнная коллСкция ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ»ΡŒΠ½Ρ‹Ρ… Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ. Доступ ΠΊ ΠΊΠ°ΠΆΠ΄ΠΎΠΌΡƒ элСмСнту осущСствляСтся посрСдством цСлочислСнного индСкса. ΠŸΠ΅Ρ€Π²Ρ‹ΠΉ элСмСнт всСгда ΠΈΠΌΠ΅Π΅Ρ‚ индСкс 0, Π²Ρ‚ΠΎΡ€ΠΎΠΉ β€” 1, ΠΈ Ρ‚Π°ΠΊ Π΄Π°Π»Π΅Π΅ Π΄ΠΎ ΠšΠΎΠ»ΠΈΡ‡Π΅ΡΡ‚Π²ΠΎ() - 1.

Если Π²Ρ‹ ΠΏΡ‹Ρ‚Π°Π΅Ρ‚Π΅ΡΡŒ ΠΎΠ±Ρ€Π°Ρ‚ΠΈΡ‚ΡŒΡΡ ΠΊ Π½Π΅ΡΡƒΡ‰Π΅ΡΡ‚Π²ΡƒΡŽΡ‰Π΅ΠΌΡƒ индСксу, систСма выдаст ΠΈΡΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΠ΅. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ ΠΏΠ΅Ρ€Π΅Π΄ Π»ΡŽΠ±Ρ‹ΠΌ ΠΎΠ±Ρ€Π°Ρ‰Π΅Π½ΠΈΠ΅ΠΌ ΠΏΠΎ Π½ΠΎΠΌΠ΅Ρ€Ρƒ Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ ΠΏΡ€ΠΎΠ²Π΅Ρ€ΡΡ‚ΡŒ Π³Ρ€Π°Π½ΠΈΡ†Ρ‹ массива. Для этого ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ ΠΌΠ΅Ρ‚ΠΎΠ΄ ΠšΠΎΠ»ΠΈΡ‡Π΅ΡΡ‚Π²ΠΎ(), ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Π²ΠΎΠ·Π²Ρ€Π°Ρ‰Π°Π΅Ρ‚ ΠΎΠ±Ρ‰Π΅Π΅ число элСмСнтов.

БтатичСская типизация Π² соврСмСнных вСрсиях ΠΏΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΡ‹ позволяСт ΠΎΠ±ΡŠΡΠ²Π»ΡΡ‚ΡŒ массивы строго ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½ΠΎΠ³ΠΎ Ρ‚ΠΈΠΏΠ°, Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€ Массив(Число). Однако ΠΌΠ΅Ρ…Π°Π½ΠΈΠ·ΠΌ индСксации остаСтся Π½Π΅ΠΈΠ·ΠΌΠ΅Π½Π½Ρ‹ΠΌ нСзависимо ΠΎΡ‚ Ρ‚ΠΎΠ³ΠΎ, Ρ…Ρ€Π°Π½ΠΈΡ‚Π΅ Π»ΠΈ Π²Ρ‹ Ρ‚Π°ΠΌ числа, строки ΠΈΠ»ΠΈ слоТныС ΠΎΠ±ΡŠΠ΅ΠΊΡ‚Ρ‹ БправочникБсылка.

⚠️ Π’Π½ΠΈΠΌΠ°Π½ΠΈΠ΅: ΠŸΠΎΠΏΡ‹Ρ‚ΠΊΠ° ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ элСмСнт ΠΏΠΎ индСксу, ΠΏΡ€Π΅Π²Ρ‹ΡˆΠ°ΡŽΡ‰Π΅ΠΌΡƒ количСство элСмСнтов минус ΠΎΠ΄ΠΈΠ½, ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Ρ‚ ΠΊ Π°Π²Π°Ρ€ΠΈΠΉΠ½ΠΎΠΌΡƒ Π·Π°Π²Π΅Ρ€ΡˆΠ΅Π½ΠΈΡŽ ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€Ρ‹. ВсСгда ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠΉΡ‚Π΅ ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΊΡƒ Π³Ρ€Π°Π½ΠΈΡ†.

Π Π°Π·ΠΌΠ΅Ρ€Π½ΠΎΡΡ‚ΡŒ массива Ρ‚Π°ΠΊΠΆΠ΅ ΠΈΠ³Ρ€Π°Π΅Ρ‚ Ρ€ΠΎΠ»ΡŒ. Π’ ΠΌΠ½ΠΎΠ³ΠΎΠΌΠ΅Ρ€Π½Ρ‹Ρ… массивах индСкс прСдставляСт собой Π½Π°Π±ΠΎΡ€ чисСл, Ρ€Π°Π·Π΄Π΅Π»Π΅Π½Π½Ρ‹Ρ… запятыми. НапримСр, доступ ΠΊ элСмСнту Π΄Π²ΡƒΠΌΠ΅Ρ€Π½ΠΎΠ³ΠΎ массива выглядит ΠΊΠ°ΠΊ Массив[0, 1].

πŸ’‘

Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠΉΡ‚Π΅ ΠΌΠ΅Ρ‚ΠΎΠ΄ ΠšΠΎΠ»ΠΈΡ‡Π΅ΡΡ‚Π²ΠΎ() Π² условиях Ρ†ΠΈΠΊΠ»ΠΎΠ², Ρ‡Ρ‚ΠΎΠ±Ρ‹ динамичСски ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΡΡ‚ΡŒ Π²Π΅Ρ€Ρ…Π½ΡŽΡŽ Π³Ρ€Π°Π½ΠΈΡ†Ρƒ, Π° Π½Π΅ Π·Π°Π΄Π°Π²Π°ΠΉΡ‚Π΅ ТСсткиС числа Π²Ρ€ΠΎΠ΄Π΅ 10 ΠΈΠ»ΠΈ 100.

ИспользованиС встроСнной Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Найти

Π‘Π°ΠΌΡ‹ΠΉ простой ΠΈ эффСктивный способ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ индСкс извСстного значСния β€” ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ Π³Π»ΠΎΠ±Π°Π»ΡŒΠ½ΡƒΡŽ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ Найти(). Она ΠΏΡ€Π΅Π΄Π½Π°Π·Π½Π°Ρ‡Π΅Π½Π° ΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎ для Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ³ΠΎ поиска элСмСнта Π² ΠΊΠΎΠ»Π»Π΅ΠΊΡ†ΠΈΠΈ ΠΈ Π²ΠΎΠ·Π²Ρ€Π°Ρ‰Π°Π΅Ρ‚ Π΅Π³ΠΎ Π½ΠΎΠΌΠ΅Ρ€ ΠΈΠ»ΠΈ НСопрСдСлСно, Ссли элСмСнт Π½Π΅ Π½Π°ΠΉΠ΄Π΅Π½.

Бинтаксис Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ ΠΏΡ€Π΅Π΄Π΅Π»ΡŒΠ½ΠΎ прост: ΠΏΠ΅Ρ€Π²Ρ‹ΠΌ Π°Ρ€Π³ΡƒΠΌΠ΅Π½Ρ‚ΠΎΠΌ пСрСдаСтся сам массив, Π²Ρ‚ΠΎΡ€Ρ‹ΠΌ β€” искомоС Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅. Ѐункция Π²ΠΎΠ·Π²Ρ€Π°Ρ‰Π°Π΅Ρ‚ число, ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰Π΅Π΅ индСксу ΠΏΠ΅Ρ€Π²ΠΎΠ³ΠΎ вхоТдСния. Если Π² массивС Π΅ΡΡ‚ΡŒ Π΄ΡƒΠ±Π»ΠΈΠΊΠ°Ρ‚Ρ‹, Π±ΡƒΠ΄Π΅Ρ‚ Π²ΠΎΠ·Π²Ρ€Π°Ρ‰Π΅Π½ индСкс самого ΠΏΠ΅Ρ€Π²ΠΎΠ³ΠΎ ΠΈΠ· Π½ΠΈΡ….

Массив = Новый Массив;

Массив.Π”ΠΎΠ±Π°Π²ΠΈΡ‚ΡŒ("Π―Π±Π»ΠΎΠΊΠΎ");

Массив.Π”ΠΎΠ±Π°Π²ΠΈΡ‚ΡŒ("Π“Ρ€ΡƒΡˆΠ°");

Массив.Π”ΠΎΠ±Π°Π²ΠΈΡ‚ΡŒ("Π‘Π»ΠΈΠ²Π°");

ИндСкс = Найти(Массив, "Π“Ρ€ΡƒΡˆΠ°");

// ИндСкс Π±ΡƒΠ΄Π΅Ρ‚ Ρ€Π°Π²Π΅Π½ 1

Π’Π°ΠΆΠ½ΠΎ ΡƒΡ‡ΠΈΡ‚Ρ‹Π²Π°Ρ‚ΡŒ, Ρ‡Ρ‚ΠΎ функция Найти() выполняСт сравнСниС Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ. Для простых Ρ‚ΠΈΠΏΠΎΠ² Π΄Π°Π½Π½Ρ‹Ρ… (числа, строки) сравнСниС Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ ΠΈΠ½Ρ‚ΡƒΠΈΡ‚ΠΈΠ²Π½ΠΎ понятно. Однако ΠΏΡ€ΠΈ Ρ€Π°Π±ΠΎΡ‚Π΅ со ссылками Π½Π° ΠΎΠ±ΡŠΠ΅ΠΊΡ‚Ρ‹ Π±Π°Π·Ρ‹ Π΄Π°Π½Π½Ρ‹Ρ… сравнСниС происходит ΠΏΠΎ ΡƒΠ½ΠΈΠΊΠ°Π»ΡŒΠ½ΠΎΠΌΡƒ ΠΈΠ΄Π΅Π½Ρ‚ΠΈΡ„ΠΈΠΊΠ°Ρ‚ΠΎΡ€Ρƒ.

  • πŸ” Ѐункция Π²ΠΎΠ·Π²Ρ€Π°Ρ‰Π°Π΅Ρ‚ НСопрСдСлСно, Ссли совпадСний Π½Π΅Ρ‚.
  • πŸ“‰ ΠŸΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ³ΠΎ поиска составляСт O(n), Ρ‡Ρ‚ΠΎ ΠΏΡ€ΠΈΠ΅ΠΌΠ»Π΅ΠΌΠΎ для ΠΌΠ°Π»Ρ‹Ρ… массивов.
  • πŸ”„ Поиск останавливаСтся Π½Π° ΠΏΠ΅Ρ€Π²ΠΎΠΌ Π½Π°ΠΉΠ΄Π΅Π½Π½ΠΎΠΌ совпадСнии.

Если Π²Π°ΠΌ Π½ΡƒΠΆΠ½ΠΎ Π½Π°ΠΉΡ‚ΠΈ всС вхоТдСния элСмСнта, Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ Найти() придСтся Π²Ρ‹Π·Ρ‹Π²Π°Ρ‚ΡŒ Π² Ρ†ΠΈΠΊΠ»Π΅, ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ Ρ€Π°Π· суТая ΠΎΠ±Π»Π°ΡΡ‚ΡŒ поиска ΠΈΠ»ΠΈ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ Π²Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅ ΠΊΠΎΠΏΠΈΠΈ массива, Ρ‡Ρ‚ΠΎ ΠΌΠ΅Π½Π΅Π΅ эффСктивно.

πŸ“Š Какой ΠΌΠ΅Ρ‚ΠΎΠ΄ поиска Π²Ρ‹ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚Π΅ Ρ‡Π°Ρ‰Π΅ всСго?
Ѐункция Найти()
Π¦ΠΈΠΊΠ» По ΠšΠ°ΠΆΠ΄ΠΎΠΌΡƒ
Π¦ΠΈΠΊΠ» Для с индСксом
Π‘Ρ‚Ρ€ΡƒΠΊΡ‚ΡƒΡ€Π°/БоотвСтствиС

Поиск индСкса Ρ‡Π΅Ρ€Π΅Π· Ρ†ΠΈΠΊΠ» с ΠΏΠ΅Ρ€Π΅Π±ΠΎΡ€ΠΎΠΌ

Π’ ситуациях, ΠΊΠΎΠ³Π΄Π° стандартная функция Найти() Π½Π΅ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ΠΈΡ‚ (Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, трСбуСтся слоТный ΠΊΡ€ΠΈΡ‚Π΅Ρ€ΠΈΠΉ поиска ΠΈΠ»ΠΈ условиС зависит ΠΎΡ‚ Π½Π΅ΡΠΊΠΎΠ»ΡŒΠΊΠΈΡ… ΠΏΠΎΠ»Π΅ΠΉ ΠΎΠ±ΡŠΠ΅ΠΊΡ‚Π°), СдинствСнным Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ΠΌ становится Ρ€ΡƒΡ‡Π½ΠΎΠΉ ΠΏΠ΅Ρ€Π΅Π±ΠΎΡ€. Для этого ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ Ρ†ΠΈΠΊΠ» Для.. Из.. По.

Π’ этом Ρ†ΠΈΠΊΠ»Π΅ пСрСмСнная-счСтчик автоматичСски ΠΏΡ€ΠΈΠ½ΠΈΠΌΠ°Π΅Ρ‚ значСния индСксов. Π­Ρ‚ΠΎ позволяСт ΠΎΠ΄Π½ΠΎΠ²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎ ΠΏΠΎΠ»ΡƒΡ‡Π°Ρ‚ΡŒ доступ ΠΊ элСмСнту ΠΈ Π·Π½Π°Ρ‚ΡŒ Π΅Π³ΠΎ Ρ‚Π΅ΠΊΡƒΡ‰ΠΈΠΉ Π½ΠΎΠΌΠ΅Ρ€. Π’Π°ΠΊΠΎΠΉ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ Π΄Π°Π΅Ρ‚ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡŒΠ½ΡƒΡŽ Π³ΠΈΠ±ΠΊΠΎΡΡ‚ΡŒ Π² написании условий.

Π˜Π½Π΄Π΅ΠΊΡΠΡƒΠΆΠ½ΠΎΠ³ΠΎΠ­Π»Π΅ΠΌΠ΅Π½Ρ‚Π° = -1;

Для ИндСкс = 0 По Массив.ΠšΠΎΠ»ΠΈΡ‡Π΅ΡΡ‚Π²ΠΎ() - 1 Π¦ΠΈΠΊΠ»

Π’Π΅ΠΊΡƒΡ‰ΠΈΠΉΠ­Π»Π΅ΠΌΠ΅Π½Ρ‚ = Массив[ИндСкс];

Если Π’Π΅ΠΊΡƒΡ‰ΠΈΠΉΠ­Π»Π΅ΠΌΠ΅Π½Ρ‚.Π¦Π΅Π½Π° > 1000 Π’ΠΎΠ³Π΄Π°

Π˜Π½Π΄Π΅ΠΊΡΠΡƒΠΆΠ½ΠΎΠ³ΠΎΠ­Π»Π΅ΠΌΠ΅Π½Ρ‚Π° = ИндСкс;

ΠŸΡ€Π΅Ρ€Π²Π°Ρ‚ΡŒ;

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

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

ИспользованиС ΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΎΡ€Π° ΠŸΡ€Π΅Ρ€Π²Π°Ρ‚ΡŒ позволяСт Π²Ρ‹ΠΉΡ‚ΠΈ ΠΈΠ· Ρ†ΠΈΠΊΠ»Π° сразу послС нахоТдСния ΠΏΠ΅Ρ€Π²ΠΎΠ³ΠΎ подходящСго элСмСнта, Ρ‡Ρ‚ΠΎ экономит рСсурсы процСссора. Π‘Π΅Π· этого ΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΎΡ€Π° Ρ†ΠΈΠΊΠ» ΠΏΡ€ΠΎΠΉΠ΄Π΅Ρ‚ Π΄ΠΎ ΠΊΠΎΠ½Ρ†Π°, ΠΈ Π²Ρ‹ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚Π΅ индСкс послСднСго подходящСго элСмСнта.

ΠŸΡ€ΠΈ Ρ€Π°Π±ΠΎΡ‚Π΅ с большими объСмами Π΄Π°Π½Π½Ρ‹Ρ… Ρ‚Π°ΠΊΠΎΠΉ ΠΌΠ΅Ρ‚ΠΎΠ΄ ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ ΠΌΠ΅Π΄Π»Π΅Π½Π½Ρ‹ΠΌ. Однако ΠΎΠ½ Π½Π΅Π·Π°ΠΌΠ΅Π½ΠΈΠΌ, ΠΊΠΎΠ³Π΄Π° Π»ΠΎΠ³ΠΈΠΊΠ° поиска Π½Π΅ сводится ΠΊ простому равСнству Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ. Π’Ρ‹ ΠΌΠΎΠΆΠ΅Ρ‚Π΅ ΠΏΡ€ΠΎΠ²Π΅Ρ€ΡΡ‚ΡŒ свойства ΠΎΠ±ΡŠΠ΅ΠΊΡ‚ΠΎΠ², ΡΡ€Π°Π²Π½ΠΈΠ²Π°Ρ‚ΡŒ Π΄Π°Ρ‚Ρ‹ ΠΈΠ»ΠΈ Π²Ρ‹ΠΏΠΎΠ»Π½ΡΡ‚ΡŒ вычислСния.

⚠️ Π’Π½ΠΈΠΌΠ°Π½ΠΈΠ΅: Π£Π±Π΅Π΄ΠΈΡ‚Π΅ΡΡŒ, Ρ‡Ρ‚ΠΎ Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ для хранСния индСкса (Π² ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ -1) явно ΡƒΠΊΠ°Π·Ρ‹Π²Π°Π΅Ρ‚ Π½Π° Ρ‚ΠΎ, Ρ‡Ρ‚ΠΎ элСмСнт Π½Π΅ Π½Π°ΠΉΠ΄Π΅Π½. НС ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠΉΡ‚Π΅ 0 ΠΊΠ°ΠΊ Ρ„Π»Π°Π³ отсутствия, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ 0 β€” это Π²Π°Π»ΠΈΠ΄Π½Ρ‹ΠΉ индСкс.

ΠΠ»ΡŒΡ‚Π΅Ρ€Π½Π°Ρ‚ΠΈΠ²ΠΎΠΉ ΠΌΠΎΠΆΠ΅Ρ‚ ΡΠ»ΡƒΠΆΠΈΡ‚ΡŒ конструкция Для ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ.. Π’.. Π¦ΠΈΠΊΠ», Π½ΠΎ Π² Π½Π΅ΠΉ пСрСмСнная Ρ†ΠΈΠΊΠ»Π° содСрТит Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ элСмСнта, Π° Π½Π΅ Π΅Π³ΠΎ индСкс. Π§Ρ‚ΠΎΠ±Ρ‹ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ Π½ΠΎΠΌΠ΅Ρ€ Π² Ρ‚Π°ΠΊΠΎΠΌ Ρ†ΠΈΠΊΠ»Π΅, придСтся Π·Π°Π²ΠΎΠ΄ΠΈΡ‚ΡŒ Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒΠ½ΡƒΡŽ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΡƒΡŽ-счСтчик ΠΈ ΡƒΠ²Π΅Π»ΠΈΡ‡ΠΈΠ²Π°Ρ‚ΡŒ Π΅Π΅ Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΈ Π²Ρ€ΡƒΡ‡Π½ΡƒΡŽ.

β˜‘οΈ Алгоритм Ρ€ΡƒΡ‡Π½ΠΎΠ³ΠΎ поиска

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

ΠžΡΠΎΠ±Π΅Π½Π½ΠΎΡΡ‚ΠΈ Ρ€Π°Π±ΠΎΡ‚Ρ‹ с Ассоциативными массивами

Часто Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊΠΈ ΠΏΡƒΡ‚Π°ΡŽΡ‚ ΠΎΠ±Ρ‹Ρ‡Π½Ρ‹Π΅ массивы ΠΈ БоотвСтствия (ассоциативныС массивы). Π’ структурС БоотвСтствиС понятиС числового индСкса отсутствуСт Π² ΠΏΡ€ΠΈΠ²Ρ‹Ρ‡Π½ΠΎΠΌ Π²ΠΈΠ΄Π΅. Π—Π΄Π΅ΡΡŒ доступ осущСствляСтся ΠΏΠΎ ΠΊΠ»ΡŽΡ‡Ρƒ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ строкой, числом ΠΈΠ»ΠΈ ΠΎΠ±ΡŠΠ΅ΠΊΡ‚ΠΎΠΌ.

Если ваша Π·Π°Π΄Π°Ρ‡Π° β€” Π½Π°ΠΉΡ‚ΠΈ "индСкс" Π² соотвСтствии, Π²Π°ΠΌ Π½ΡƒΠΆΠ½ΠΎ ΠΏΠΎΠ½ΠΈΠΌΠ°Ρ‚ΡŒ, Ρ‡Ρ‚ΠΎ Π²Ρ‹ ΠΈΡ‰Π΅Ρ‚Π΅ ΠΊΠ»ΡŽΡ‡. ΠœΠ΅Ρ‚ΠΎΠ΄ Найти() для соотвСтствия Π²ΠΎΠ·Π²Ρ€Π°Ρ‰Π°Π΅Ρ‚ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ ΠΏΠΎ ΠΊΠ»ΡŽΡ‡Ρƒ, Π° Π½Π΅ ΠΏΠΎΠ·ΠΈΡ†ΠΈΡŽ. ΠŸΠΎΠ·ΠΈΡ†ΠΈΡ элСмСнта Π² соотвСтствии Π½Π΅ гарантируСтся ΠΈ ΠΌΠΎΠΆΠ΅Ρ‚ ΠΌΠ΅Π½ΡΡ‚ΡŒΡΡ ΠΏΡ€ΠΈ Π΄ΠΎΠ±Π°Π²Π»Π΅Π½ΠΈΠΈ Π½ΠΎΠ²Ρ‹Ρ… ΠΏΠ°Ρ€ ΠΊΠ»ΡŽΡ‡-Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅.

Π’Π΅ΠΌ Π½Π΅ ΠΌΠ΅Π½Π΅Π΅, Ссли Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ список всСх ΠΊΠ»ΡŽΡ‡Π΅ΠΉ ΠΈ Π½Π°ΠΉΡ‚ΠΈ ΠΏΠΎΠ·ΠΈΡ†ΠΈΡŽ ΠΊΠΎΠ½ΠΊΡ€Π΅Ρ‚Π½ΠΎΠ³ΠΎ ΠΊΠ»ΡŽΡ‡Π° Π² этом спискС, ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΠΎΠ²Π°Ρ‚ΡŒ ΠΊΠ»ΡŽΡ‡ΠΈ Π² ΠΎΠ±Ρ‹Ρ‡Π½Ρ‹ΠΉ массив. Ѐункция ΠšΠ»ΡŽΡ‡ΠΈ() Π²ΠΎΠ·Π²Ρ€Π°Ρ‰Π°Π΅Ρ‚ массив всСх ΠΊΠ»ΡŽΡ‡Π΅ΠΉ соотвСтствия, с ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΌ ΡƒΠΆΠ΅ ΠΌΠΎΠΆΠ½ΠΎ Ρ€Π°Π±ΠΎΡ‚Π°Ρ‚ΡŒ стандартными ΠΌΠ΅Ρ‚ΠΎΠ΄Π°ΠΌΠΈ.

Π’ΠΈΠΏ ΠΊΠΎΠ»Π»Π΅ΠΊΡ†ΠΈΠΈ Π’ΠΈΠΏ индСкса/ΠΊΠ»ΡŽΡ‡Π° ΠœΠ΅Ρ‚ΠΎΠ΄ доступа Π£ΠΏΠΎΡ€ΡΠ΄ΠΎΡ‡Π΅Π½Π½ΠΎΡΡ‚ΡŒ
Массив Число (0, 1, 2..) По индСксу [i] Π‘Ρ‚Ρ€ΠΎΠ³ΠΎ сохранСна
БоотвСтствиС ΠŸΡ€ΠΎΠΈΠ·Π²ΠΎΠ»ΡŒΠ½Ρ‹ΠΉ Ρ‚ΠΈΠΏ По ΠΊΠ»ΡŽΡ‡Ρƒ [ΠšΠ»ΡŽΡ‡] НС Π³Π°Ρ€Π°Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π°
Π‘Ρ‚Ρ€ΡƒΠΊΡ‚ΡƒΡ€Π° Π‘Ρ‚Ρ€ΠΎΠΊΠ° (имя свойства) По ΠΈΠΌΠ΅Π½ΠΈ Бвойство НС ΠΏΡ€ΠΈΠΌΠ΅Π½ΠΈΠΌΠΎ
Π’Π°Π±Π»ΠΈΡ†Π° Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ Число ΠΈΠ»ΠΈ строка По индСксу ΠΈΠ»ΠΈ ΠΈΠΌΠ΅Π½ΠΈ ΠΊΠΎΠ»ΠΎΠ½ΠΊΠΈ Π‘ΠΎΡ…Ρ€Π°Π½Π΅Π½Π°

ИспользованиС БоотвСтствия ΠΎΠΏΡ€Π°Π²Π΄Π°Π½ΠΎ, ΠΊΠΎΠ³Π΄Π° доступ ΠΊ Π΄Π°Π½Π½Ρ‹ΠΌ Π΄ΠΎΠ»ΠΆΠ΅Π½ ΠΎΡΡƒΡ‰Π΅ΡΡ‚Π²Π»ΡΡ‚ΡŒΡΡ ΠΏΠΎ ΡƒΠ½ΠΈΠΊΠ°Π»ΡŒΠ½ΠΎΠΌΡƒ ΠΈΠ΄Π΅Π½Ρ‚ΠΈΡ„ΠΈΠΊΠ°Ρ‚ΠΎΡ€Ρƒ, Π° Π½Π΅ ΠΏΠΎ порядковому Π½ΠΎΠΌΠ΅Ρ€Ρƒ. Π­Ρ‚ΠΎ ускоряСт Π²Ρ‹Π±ΠΎΡ€ΠΊΡƒ Π² Π±ΠΎΠ»ΡŒΡˆΠΈΡ… Π½Π°Π±ΠΎΡ€Π°Ρ… Π΄Π°Π½Π½Ρ‹Ρ…, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ поиск ΠΏΠΎ Ρ…Π΅Ρˆ-Ρ‚Π°Π±Π»ΠΈΡ†Π΅ быстрСС Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ³ΠΎ ΠΏΠ΅Ρ€Π΅Π±ΠΎΡ€Π°.

ΠŸΡ€ΠΈ ΠΏΠΎΠΏΡ‹Ρ‚ΠΊΠ΅ ΠΏΡ€ΠΈΠΌΠ΅Π½ΠΈΡ‚ΡŒ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ Найти() ΠΊ ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΠΈΡŽ, ΠΏΠ΅Ρ€Π΅Π΄Π°Π² Ρ‚ΡƒΠ΄Π° Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ вмСсто ΠΊΠ»ΡŽΡ‡Π°, Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ Π±ΡƒΠ΄Π΅Ρ‚ нСпрСдсказуСмым ΠΈΠ»ΠΈ функция Π²Π΅Ρ€Π½Π΅Ρ‚ НСопрСдСлСно, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ ΠΎΠ½Π° ΠΈΡ‰Π΅Ρ‚ ΠΊΠ»ΡŽΡ‡, Ρ€Π°Π²Π½Ρ‹ΠΉ ΠΏΠ΅Ρ€Π΅Π΄Π°Π½Π½ΠΎΠΌΡƒ Π·Π½Π°Ρ‡Π΅Π½ΠΈΡŽ.

ΠŸΠΎΡ‡Π΅ΠΌΡƒ порядок Π² БоотвСтствии Π²Π°ΠΆΠ΅Π½?

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

ΠžΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ° ошибок ΠΈ отсутствиС элСмСнта

ΠšΠ»ΡŽΡ‡Π΅Π²ΠΎΠΉ ΠΌΠΎΠΌΠ΅Π½Ρ‚ ΠΏΡ€ΠΈ поискС индСкса β€” коррСктная ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ° ситуации, ΠΊΠΎΠ³Π΄Π° элСмСнт Π½Π΅ Π½Π°ΠΉΠ΄Π΅Π½. Ѐункция Найти() Π²ΠΎΠ·Π²Ρ€Π°Ρ‰Π°Π΅Ρ‚ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Ρ‚ΠΈΠΏΠ° НСопрСдСлСно. ΠŸΡ€ΡΠΌΠΎΠ΅ использованиС этого Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π° Π² качСствС индСкса массива Π²Ρ‹Π·ΠΎΠ²Π΅Ρ‚ ΠΎΡˆΠΈΠ±ΠΊΡƒ.

ВсСгда провСряйтС Ρ‚ΠΈΠΏ Π²ΠΎΠ·Π²Ρ€Π°Ρ‰Π°Π΅ΠΌΠΎΠ³ΠΎ значСния ΠΏΠ΅Ρ€Π΅Π΄ использованиСм. ΠšΠΎΠ½ΡΡ‚Ρ€ΡƒΠΊΡ†ΠΈΡ Π’ΠΈΠΏΠ—Π½Ρ‡() ΠΈΠ»ΠΈ ΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΎΡ€ Если.. = НСопрСдСлСно Π’ΠΎΠ³Π΄Π° ΡΠ²Π»ΡΡŽΡ‚ΡΡ стандартными ΠΏΠ°Ρ‚Ρ‚Π΅Ρ€Π½Π°ΠΌΠΈ Π·Π°Ρ‰ΠΈΡ‚Ρ‹ ΠΊΠΎΠ΄Π°.

ИндСкс = Найти(Массив, Π˜ΡΠΊΠΎΠΌΠΎΠ΅Π—Π½Π°Ρ‡Π΅Π½ΠΈΠ΅);

Если ИндСкс = НСопрСдСлСно Π’ΠΎΠ³Π΄Π°

Π‘ΠΎΠΎΠ±Ρ‰ΠΈΡ‚ΡŒ("Π­Π»Π΅ΠΌΠ΅Π½Ρ‚ Π½Π΅ Π½Π°ΠΉΠ΄Π΅Π½!");

Π’ΠΎΠ·Π²Ρ€Π°Ρ‚;

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

// Π”Π°Π»ΡŒΠ½Π΅ΠΉΡˆΠ°Ρ Ρ€Π°Π±ΠΎΡ‚Π° с Массив[ИндСкс]

Π’ цикличСском поискС ситуация Π°Π½Π°Π»ΠΎΠ³ΠΈΡ‡Π½Π°. Если Ρ†ΠΈΠΊΠ» Π·Π°Π²Π΅Ρ€ΡˆΠΈΠ»ΡΡ, Π° Ρ„Π»Π°Π³ нахоТдСния Π½Π΅ Π±Ρ‹Π» установлСн, пСрСмСнная индСкса останСтся Π² исходном состоянии (Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, -1). Π­Ρ‚ΠΎ состояниС Π½ΡƒΠΆΠ½ΠΎ явно ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚Π°Ρ‚ΡŒ.

Π˜Π³Π½ΠΎΡ€ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΊΠΈ Π½Π° сущСствованиС элСмСнта β€” ΠΎΠ΄Π½Π° ΠΈΠ· самых частых ΠΏΡ€ΠΈΡ‡ΠΈΠ½ ошибок Π² Ρ‚ΠΈΠΏΠΎΠ²Ρ‹Ρ… конфигурациях. ОсобСнно это Π°ΠΊΡ‚ΡƒΠ°Π»ΡŒΠ½ΠΎ ΠΏΡ€ΠΈ Ρ€Π°Π±ΠΎΡ‚Π΅ с Π΄Π°Π½Π½Ρ‹ΠΌΠΈ, ΠΏΡ€ΠΈΡˆΠ΅Π΄ΡˆΠΈΠΌΠΈ ΠΈΠ· Π²Π½Π΅ΡˆΠ½ΠΈΡ… источников, Π³Π΄Π΅ состав массива Π½Π΅ Π³Π°Ρ€Π°Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½.

  • βœ… ВсСгда провСряйтС Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Найти().
  • πŸ›‘ Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠΉΡ‚Π΅ ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΡƒ ΠΈΡΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΠΉ ΠŸΠΎΠΏΡ‹Ρ‚ΠΊΠ°..Π˜ΡΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΠ΅ для критичСских участков.
  • πŸ“ Π›ΠΎΠ³ΠΈΡ€ΡƒΠΉΡ‚Π΅ случаи отсутствия ΠΎΠΆΠΈΠ΄Π°Π΅ΠΌΡ‹Ρ… элСмСнтов для ΠΎΡ‚Π»Π°Π΄ΠΊΠΈ.

⚠️ Π’Π½ΠΈΠΌΠ°Π½ΠΈΠ΅: Π˜Π½Ρ‚Π΅Ρ€Ρ„Π΅ΠΉΡ ΠΈ ΠΏΠΎΠ²Π΅Π΄Π΅Π½ΠΈΠ΅ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠ² ΠΌΠΎΠ³ΡƒΡ‚ Π½Π΅Π·Π½Π°Ρ‡ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ ΠΎΡ‚Π»ΠΈΡ‡Π°Ρ‚ΡŒΡΡ Π² зависимости ΠΎΡ‚ вСрсии ΠΏΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΡ‹ 1Π‘ ΠΈ Ρ€Π΅ΠΆΠΈΠΌΠ° запуска (ΠΎΠ±Ρ‹Ρ‡Π½ΠΎΠ΅ ΠΏΡ€ΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅, Π²Π΅Π±-ΠΊΠ»ΠΈΠ΅Π½Ρ‚, толстый ΠΊΠ»ΠΈΠ΅Π½Ρ‚). БвСряйтС синтаксис-ΠΏΠΎΠΌΠΎΡ‰Π½ΠΈΠΊ для вашСй ΠΊΠΎΠ½ΠΊΡ€Π΅Ρ‚Π½ΠΎΠΉ вСрсии.

πŸ’‘

БСзопасный ΠΊΠΎΠ΄ всСгда ΠΏΡ€Π΅Π΄ΠΏΠΎΠ»Π°Π³Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ элСмСнт ΠΌΠΎΠΆΠ΅Ρ‚ ΠΎΡ‚ΡΡƒΡ‚ΡΡ‚Π²ΠΎΠ²Π°Ρ‚ΡŒ. ΠžΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ° случая "Π½Π΅ Π½Π°ΠΉΠ΄Π΅Π½ΠΎ" Π²Π°ΠΆΠ½Π΅Π΅, Ρ‡Π΅ΠΌ ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ° случая "Π½Π°ΠΉΠ΄Π΅Π½ΠΎ".

ΠžΠΏΡ‚ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΡ поиска Π² Π±ΠΎΠ»ΡŒΡˆΠΈΡ… коллСкциях

Когда Ρ€Π°Π·ΠΌΠ΅Ρ€ массива исчисляСтся тысячами ΠΈΠ»ΠΈ ΠΌΠΈΠ»Π»ΠΈΠΎΠ½Π°ΠΌΠΈ строк, Π»ΠΈΠ½Π΅ΠΉΠ½Ρ‹ΠΉ поиск становится ΡƒΠ·ΠΊΠΈΠΌ мСстом ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ. ВрСмя выполнСния ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ растСт ΠΏΡ€ΠΎΠΏΠΎΡ€Ρ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½ΠΎ Ρ€Π°Π·ΠΌΠ΅Ρ€Ρƒ Π΄Π°Π½Π½Ρ‹Ρ…. Π’ Ρ‚Π°ΠΊΠΈΡ… случаях стоит ΠΏΠ΅Ρ€Π΅ΡΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Π°Ρ€Ρ…ΠΈΡ‚Π΅ΠΊΡ‚ΡƒΡ€Ρƒ хранСния Π΄Π°Π½Π½Ρ‹Ρ….

Если поиск ΠΏΠΎ Π·Π½Π°Ρ‡Π΅Π½ΠΈΡŽ выполняСтся часто, цСлСсообразно ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ БоотвСтствиС вмСсто массива. Вставка ΠΈ поиск Π² соотвСтствии Ρ€Π°Π±ΠΎΡ‚Π°ΡŽΡ‚ Π·Π° константноС врСмя O(1) Π² срСднСм случаС, Ρ‡Ρ‚ΠΎ Π΄Π°Π΅Ρ‚ ΠΊΠΎΠ»ΠΎΡΡΠ°Π»ΡŒΠ½Ρ‹ΠΉ Π²Ρ‹ΠΈΠ³Ρ€Ρ‹Ρˆ Π½Π° Π±ΠΎΠ»ΡŒΡˆΠΈΡ… ΠΎΠ±ΡŠΠ΅ΠΌΠ°Ρ….

Π’Π°ΠΊΠΆΠ΅ ΠΌΠΎΠΆΠ½ΠΎ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ ΠΈΠ½Π΄Π΅ΠΊΡΠ°Ρ†ΠΈΡŽ Π½Π° сторонС Π±Π°Π·Ρ‹ Π΄Π°Π½Π½Ρ‹Ρ…, Ссли Π΄Π°Π½Π½Ρ‹Π΅ хранятся Π² рСгистрах ΠΈΠ»ΠΈ Ρ‚Π°Π±Π»ΠΈΡ‡Π½Ρ‹Ρ… частях Π΄ΠΎΠΊΡƒΠΌΠ΅Π½Ρ‚ΠΎΠ². Π’Ρ‹Π±ΠΎΡ€ΠΊΠ° Ρ‡Π΅Ρ€Π΅Π· запрос с условиСм Π“Π”Π• Π±ΡƒΠ΄Π΅Ρ‚ Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½Π° Π΄Π²ΠΈΠΆΠΊΠΎΠΌ Π‘Π£Π‘Π” Π³ΠΎΡ€Π°Π·Π΄ΠΎ быстрСС, Ρ‡Π΅ΠΌ ΠΏΠ΅Ρ€Π΅Π±ΠΎΡ€ Π² ΠΊΠΎΠ΄Π΅ 1Π‘.

Для сортированных массивов Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡ€ΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Π±ΠΈΠ½Π°Ρ€Π½ΠΎΠ³ΠΎ поиска, хотя встроСнных срСдств для этого Π² языкС 1Π‘ Π½Π΅Ρ‚. РСализация Π±ΠΈΠ½Π°Ρ€Π½ΠΎΠ³ΠΎ поиска Π²Ρ€ΡƒΡ‡Π½ΡƒΡŽ Ρ‚Ρ€Π΅Π±ΡƒΠ΅Ρ‚ Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹Ρ… усилий, Π½ΠΎ сокращаСт количСство ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΉ с N Π΄ΠΎ log2(N).

πŸ’‘

Если Π²Ρ‹ Ρ„ΠΎΡ€ΠΌΠΈΡ€ΡƒΠ΅Ρ‚Π΅ массив для ΠΏΠΎΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅Π³ΠΎ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡ€Π°Ρ‚Π½ΠΎΠ³ΠΎ поиска, ΠΏΠΎΡ‚Ρ€Π°Ρ‚ΡŒΡ‚Π΅ врСмя Π½Π° ΠΏΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΠΎΠ²Π°Π½ΠΈΠ΅ Π΅Π³ΠΎ Π² БоотвСтствиС. Π—Π°Ρ‚Ρ€Π°Ρ‚Ρ‹ Π½Π° построСниС окупятся ΠΏΡ€ΠΈ ΠΏΠ΅Ρ€Π²ΠΎΠΌ ΠΆΠ΅ поискС Π² большой ΠΊΠΎΠ»Π»Π΅ΠΊΡ†ΠΈΠΈ.

Π§Ρ‚ΠΎ Π²ΠΎΠ·Π²Ρ€Π°Ρ‰Π°Π΅Ρ‚ функция Найти, Ссли Π² массивС нСсколько ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹Ρ… элСмСнтов?

Ѐункция Π²ΠΎΠ·Π²Ρ€Π°Ρ‰Π°Π΅Ρ‚ индСкс самого ΠΏΠ΅Ρ€Π²ΠΎΠ³ΠΎ Π½Π°ΠΉΠ΄Π΅Π½Π½ΠΎΠ³ΠΎ элСмСнта, считая с Π½Π°Ρ‡Π°Π»Π° массива (ΠΎΡ‚ нуля). Поиск прСкращаСтся сразу послС ΠΏΠ΅Ρ€Π²ΠΎΠ³ΠΎ совпадСния.

МоТно Π»ΠΈ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ ΠΎΡ‚Ρ€ΠΈΡ†Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹Π΅ индСксы Π² массивах 1Π‘?

НСт, Π² языкС 1Π‘ ΠΎΡ‚Ρ€ΠΈΡ†Π°Ρ‚Π΅Π»ΡŒΠ½Π°Ρ индСксация (ΠΊΠ°ΠΊ Π² Python, Π³Π΄Π΅ -1 ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚ послСдний элСмСнт) Π½Π΅ поддСрТиваСтся. ΠŸΠΎΠΏΡ‹Ρ‚ΠΊΠ° ΠΎΠ±Ρ€Π°Ρ‚ΠΈΡ‚ΡŒΡΡ ΠΏΠΎ ΠΎΡ‚Ρ€ΠΈΡ†Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΠΌΡƒ индСксу Π²Ρ‹Π·ΠΎΠ²Π΅Ρ‚ ΠΎΡˆΠΈΠ±ΠΊΡƒ выполнСния.

Как Π½Π°ΠΉΡ‚ΠΈ индСкс элСмСнта Π² Π’Π°Π±Π»ΠΈΡ†Π΅ Π—Π½Π°Ρ‡Π΅Π½ΠΈΠΉ?

Для Π’Π°Π±Π»ΠΈΡ†Ρ‹ Π—Π½Π°Ρ‡Π΅Π½ΠΈΠΉ Ρ‚Π°ΠΊΠΆΠ΅ Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ функция Найти(Π’Π°Π±Π»ΠΈΡ†Π°, Π‘Ρ‚Ρ€ΠΎΠΊΠ°). Она Π²Π΅Ρ€Π½Π΅Ρ‚ индСкс строки. Если Π½ΡƒΠΆΠ½ΠΎ Π½Π°ΠΉΡ‚ΠΈ ΠΏΠΎΠ·ΠΈΡ†ΠΈΡŽ ΠΏΠΎ Π·Π½Π°Ρ‡Π΅Π½ΠΈΡŽ Π² ΠΊΠΎΠ»ΠΎΠ½ΠΊΠ΅, ΡƒΠ΄ΠΎΠ±Π½Π΅Π΅ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ ΠΌΠ΅Ρ‚ΠΎΠ΄ Π’Π°Π±Π»ΠΈΡ†Π°.НайтиБтроки(ΠžΡ‚Π±ΠΎΡ€) ΠΈ Π²Π·ΡΡ‚ΡŒ индСкс ΠΏΠ΅Ρ€Π²ΠΎΠΉ строки ΠΈΠ· Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π°.

Π’ Ρ‡Π΅ΠΌ Ρ€Π°Π·Π½ΠΈΡ†Π° ΠΌΠ΅ΠΆΠ΄Ρƒ Найти() ΠΈ ИндСкс()?

Π’ языкС 1Π‘ Π½Π΅Ρ‚ глобальной Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ ИндСкс() для массивов. Π•ΡΡ‚ΡŒ ΠΌΠ΅Ρ‚ΠΎΠ΄ ИндСкс() Ρƒ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… ΠΎΠ±ΡŠΠ΅ΠΊΡ‚ΠΎΠ², Π½ΠΎ стандартным способом поиска ΠΏΠΎΠ·ΠΈΡ†ΠΈΠΈ Π² ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ»ΡŒΠ½ΠΎΠΌ массивС являСтся ΠΈΠΌΠ΅Π½Π½ΠΎ функция Найти().

Как ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ послСдний индСкс массива?

ПослСдний индСкс всСгда Ρ€Π°Π²Π΅Π½ Массив.ΠšΠΎΠ»ΠΈΡ‡Π΅ΡΡ‚Π²ΠΎ() - 1. Если массив пуст, количСство Ρ€Π°Π²Π½ΠΎ 0, ΠΈ ΠΊΠΎΡ€Ρ€Π΅ΠΊΡ‚Π½ΠΎΠ³ΠΎ индСкса Π½Π΅ сущСствуСт.