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

Π’ зависимости ΠΎΡ‚ вСрсии ΠΏΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΡ‹ ΠΈ Ρ‚ΠΈΠΏΠ° ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΠΎΠΉ ΠΊΠΎΠ»Π»Π΅ΠΊΡ†ΠΈΠΈ, ΠΏΠΎΠ΄Ρ…ΠΎΠ΄Ρ‹ ΠΊ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡŽ этой Π·Π°Π΄Π°Ρ‡ΠΈ ΠΌΠΎΠ³ΡƒΡ‚ сущСствСнно Ρ€Π°Π·Π»ΠΈΡ‡Π°Ρ‚ΡŒΡΡ. Π’ Ρ€Π°Π½Π½ΠΈΡ… вСрсиях Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊΠΈ Π±Ρ‹Π»ΠΈ Π²Ρ‹Π½ΡƒΠΆΠ΄Π΅Π½Ρ‹ ΠΏΠΈΡΠ°Ρ‚ΡŒ Π³Ρ€ΠΎΠΌΠΎΠ·Π΄ΠΊΠΈΠ΅ Ρ†ΠΈΠΊΠ»Ρ‹, Ρ‚ΠΎΠ³Π΄Π° ΠΊΠ°ΠΊ соврСмСнныС Ρ€Π΅Π»ΠΈΠ·Ρ‹ ΠΏΡ€Π΅Π΄ΠΎΡΡ‚Π°Π²Π»ΡΡŽΡ‚ ΠΌΠΎΡ‰Π½Ρ‹Π΅ встроСнныС инструмСнты. ПониманиС Ρ€Π°Π·Π½ΠΈΡ†Ρ‹ ΠΌΠ΅ΠΆΠ΄Ρƒ ΠΌΠ΅Ρ‚ΠΎΠ΄Π°ΠΌΠΈ Найти(), ΠΠ°ΠΉΡ‚ΠΈΠ˜Π½Π΄Π΅ΠΊΡ() ΠΈ Ρ€ΡƒΡ‡Π½Ρ‹ΠΌ ΠΏΠ΅Ρ€Π΅Π±ΠΎΡ€ΠΎΠΌ ΠΏΠΎΠ·Π²ΠΎΠ»ΠΈΡ‚ Π²Π°ΠΌ Π²Ρ‹Π±ΠΈΡ€Π°Ρ‚ΡŒ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ эффСктивноС Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ для ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΊΠΎΠ½ΠΊΡ€Π΅Ρ‚Π½ΠΎΠΉ ситуации.

Рассмотрим Π΄Π΅Ρ‚Π°Π»ΡŒΠ½ΠΎ всС доступныС способы, ΠΈΡ… прСимущСства ΠΈ скрытыС ΠΏΠΎΠ΄Π²ΠΎΠ΄Π½Ρ‹Π΅ ΠΊΠ°ΠΌΠ½ΠΈ. ΠœΡ‹ Ρ€Π°Π·Π±Π΅Ρ€Π΅ΠΌ ΠΊΠ°ΠΊ Ρ€Π°Π±ΠΎΡ‚Ρƒ с ΠΎΠ±Ρ‹Ρ‡Π½Ρ‹ΠΌΠΈ массивами, Ρ‚Π°ΠΊ ΠΈ со спСциализированными коллСкциями, Ρ‚Π°ΠΊΠΈΠΌΠΈ ΠΊΠ°ΠΊ списки Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ. ОсобоС Π²Π½ΠΈΠΌΠ°Π½ΠΈΠ΅ ΡƒΠ΄Π΅Π»ΠΈΠΌ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ ΠΏΡ€ΠΈ Ρ€Π°Π±ΠΎΡ‚Π΅ с тысячами записСй Π²Ρ‹Π±ΠΎΡ€ Π½Π΅ΠΏΡ€Π°Π²ΠΈΠ»ΡŒΠ½ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ΠΌΠΎΠΆΠ΅Ρ‚ Π·Π°ΠΌΠ΅Π΄Π»ΠΈΡ‚ΡŒ Ρ€Π°Π±ΠΎΡ‚Ρƒ систСмы Π² Ρ€Π°Π·Ρ‹.

ВстроСнныС ΠΌΠ΅Ρ‚ΠΎΠ΄Ρ‹ поиска индСкса Π² соврСмСнных вСрсиях

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

Π’Π°ΠΆΠ½ΠΎ ΠΏΠΎΠ½ΠΈΠΌΠ°Ρ‚ΡŒ, Ρ‡Ρ‚ΠΎ индСксация Π² 1Π‘ начинаСтся с нуля. Π­Ρ‚ΠΎ ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ ΠΏΠ΅Ρ€Π²Ρ‹ΠΉ элСмСнт массива ΠΈΠΌΠ΅Π΅Ρ‚ индСкс 0, Π²Ρ‚ΠΎΡ€ΠΎΠΉ β€” 1, ΠΈ Ρ‚Π°ΠΊ Π΄Π°Π»Π΅Π΅. ΠœΠ΅Ρ‚ΠΎΠ΄ ΠΠ°ΠΉΡ‚ΠΈΠ˜Π½Π΄Π΅ΠΊΡ автоматичСски ΡƒΡ‡ΠΈΡ‚Ρ‹Π²Π°Π΅Ρ‚ эту ΠΎΡΠΎΠ±Π΅Π½Π½ΠΎΡΡ‚ΡŒ ΠΈ Π²ΠΎΠ·Π²Ρ€Π°Ρ‰Π°Π΅Ρ‚ цСлочислСнноС Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅. Если элСмСнт Π½Π΅ Π½Π°ΠΉΠ΄Π΅Π½, ΠΌΠ΅Ρ‚ΠΎΠ΄ Π²Π΅Ρ€Π½Π΅Ρ‚ -1, Ρ‡Ρ‚ΠΎ являСтся стандартной ΠΏΡ€Π°ΠΊΡ‚ΠΈΠΊΠΎΠΉ Π²ΠΎ ΠΌΠ½ΠΎΠ³ΠΈΡ… языках программирования ΠΈ позволяСт Π»Π΅Π³ΠΊΠΎ ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΈΡ‚ΡŒ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ Π² условном ΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΎΡ€Π΅.

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

⚠️ Π’Π½ΠΈΠΌΠ°Π½ΠΈΠ΅: ΠœΠ΅Ρ‚ΠΎΠ΄ ΠΠ°ΠΉΡ‚ΠΈΠ˜Π½Π΄Π΅ΠΊΡ() доступСн Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π² ΠΏΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΠ΅ 1Π‘ 8.3 ΠΈ Π²Ρ‹ΡˆΠ΅. ΠŸΡ€ΠΈ ΠΏΠΎΠΏΡ‹Ρ‚ΠΊΠ΅ использования этого ΠΊΠΎΠ΄Π° Π² срСдС 8.2 Π²Ρ‹ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚Π΅ ΠΎΡˆΠΈΠ±ΠΊΡƒ компиляции. ВсСгда провСряйтС ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½ΡƒΡŽ Π²Π΅Ρ€ΡΠΈΡŽ ΠΏΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΡ‹, ΠΏΠΎΠ΄Π΄Π΅Ρ€ΠΆΠΈΠ²Π°Π΅ΠΌΡƒΡŽ вашСй ΠΊΠΎΠ½Ρ„ΠΈΠ³ΡƒΡ€Π°Ρ†ΠΈΠ΅ΠΉ, ΠΏΠ΅Ρ€Π΅Π΄ Π²Π½Π΅Π΄Ρ€Π΅Π½ΠΈΠ΅ΠΌ Π½ΠΎΠ²Ρ‹Ρ… Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ.

Для слоТных ΠΎΠ±ΡŠΠ΅ΠΊΡ‚ΠΎΠ², Ρ‚Π°ΠΊΠΈΡ… ΠΊΠ°ΠΊ структуры ΠΈΠ»ΠΈ соотвСтствия, поиск ΠΏΠΎ Π·Π½Π°Ρ‡Π΅Π½ΠΈΡŽ ΠΌΠΎΠΆΠ΅Ρ‚ Ρ€Π°Π±ΠΎΡ‚Π°Ρ‚ΡŒ Π½Π΅ Ρ‚Π°ΠΊ, ΠΊΠ°ΠΊ оТидаСтся. Π’ Ρ‚Π°ΠΊΠΈΡ… случаях систСма сравниваСт ссылки Π½Π° ΠΎΠ±ΡŠΠ΅ΠΊΡ‚Ρ‹ ΠΈΠ»ΠΈ ΠΈΡ… Π²Π½ΡƒΡ‚Ρ€Π΅Π½Π½Π΅Π΅ прСдставлСниС. РСкомСндуСтся ΠΏΡ€Π΅Π΄Π²Π°Ρ€ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ Ρ‚Π΅ΡΡ‚ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ ΠΏΠΎΠ²Π΅Π΄Π΅Π½ΠΈΠ΅ ΠΌΠ΅Ρ‚ΠΎΠ΄Π° Π½Π° тСстовых Π΄Π°Π½Π½Ρ‹Ρ…, особСнно Ссли массив содСрТит Π½Π΅ΠΎΠ΄Π½ΠΎΡ€ΠΎΠ΄Π½Ρ‹Π΅ Ρ‚ΠΈΠΏΡ‹ Π΄Π°Π½Π½Ρ‹Ρ….

πŸ’‘

ИспользованиС встроСнного ΠΌΠ΅Ρ‚ΠΎΠ΄Π° ΠΠ°ΠΉΡ‚ΠΈΠ˜Π½Π΄Π΅ΠΊΡ() сокращаСт объСм ΠΊΠΎΠ΄Π° ΠΈ ΠΏΠΎΠ²Ρ‹ΡˆΠ°Π΅Ρ‚ Ρ‡ΠΈΡ‚Π°Π΅ΠΌΠΎΡΡ‚ΡŒ, Π½ΠΎ Ρ‚Ρ€Π΅Π±ΡƒΠ΅Ρ‚ вСрсии ΠΏΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΡ‹ Π½Π΅ Π½ΠΈΠΆΠ΅ 8.3.

ΠšΠ»Π°ΡΡΠΈΡ‡Π΅ΡΠΊΠΈΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ поиска Ρ‡Π΅Ρ€Π΅Π· Ρ†ΠΈΠΊΠ»

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

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

ИндСкс = -1;

Для Π‘Ρ‡Π΅Ρ‚Ρ‡ΠΈΠΊ = 0 По Массив.Π’Π“Ρ€Π°Π½ΠΈΡ†Π°() Π¦ΠΈΠΊΠ»

Если Массив[Π‘Ρ‡Π΅Ρ‚Ρ‡ΠΈΠΊ] = Π˜ΡΠΊΠΎΠΌΠΎΠ΅Π—Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Π’ΠΎΠ³Π΄Π°

ИндСкс = Π‘Ρ‡Π΅Ρ‚Ρ‡ΠΈΠΊ;

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

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

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

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

πŸ“Š Какой ΠΌΠ΅Ρ‚ΠΎΠ΄ поиска Π²Ρ‹ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚Π΅ Ρ‡Π°Ρ‰Π΅?
ВстроСнный ΠΠ°ΠΉΡ‚ΠΈΠ˜Π½Π΄Π΅ΠΊΡ
Π¦ΠΈΠΊΠ» Для
Цикл Пока
Ѐункция Найти

ΠžΡΠΎΠ±Π΅Π½Π½ΠΎΡΡ‚ΠΈ Ρ€Π°Π±ΠΎΡ‚Ρ‹ с массивом БписокЗначСний

ΠšΠΎΠ»Π»Π΅ΠΊΡ†ΠΈΡ БписокЗначСний являСтся ΠΎΠ΄Π½ΠΎΠΉ ΠΈΠ· самых популярных структур Π΄Π°Π½Π½Ρ‹Ρ… Π² 1Π‘, часто ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΠ°Ρ для хранСния ΠΏΠ°Ρ€Π°ΠΌΠ΅Ρ‚Ρ€ΠΎΠ² ΠΎΡ‚Ρ‡Π΅Ρ‚ΠΎΠ² ΠΈ настроСк Ρ„ΠΎΡ€ΠΌ. Π₯отя ΠΎΠ½Π° Π²ΠΈΠ·ΡƒΠ°Π»ΡŒΠ½ΠΎ ΠΏΠΎΡ…ΠΎΠΆΠ° Π½Π° ΠΎΠ±Ρ‹Ρ‡Π½Ρ‹ΠΉ массив, внутрСнняя рСализация ΠΈ доступныС ΠΌΠ΅Ρ‚ΠΎΠ΄Ρ‹ ΠΈΠΌΠ΅ΡŽΡ‚ свои особСнности. Поиск индСкса здСсь ΠΌΠΎΠΆΠ΅Ρ‚ Π²Ρ‹ΠΏΠΎΠ»Π½ΡΡ‚ΡŒΡΡ ΠΊΠ°ΠΊ ΠΏΠΎ Π·Π½Π°Ρ‡Π΅Π½ΠΈΡŽ, Ρ‚Π°ΠΊ ΠΈ ΠΏΠΎ ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²Π»Π΅Π½ΠΈΡŽ элСмСнта.

ΠœΠ΅Ρ‚ΠΎΠ΄ ΠΠ°ΠΉΡ‚ΠΈΠŸΠΎΠ—Π½Π°Ρ‡Π΅Π½ΠΈΡŽ Π²ΠΎΠ·Π²Ρ€Π°Ρ‰Π°Π΅Ρ‚ Π½Π΅ индСкс, Π° сам элСмСнт ΠΊΠΎΠ»Π»Π΅ΠΊΡ†ΠΈΠΈ, Ссли ΠΎΠ½ Π½Π°ΠΉΠ΄Π΅Π½. Π§Ρ‚ΠΎΠ±Ρ‹ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ индСкс, Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ Π²ΠΎΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒΡΡ ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠΌ ИндСкс(), ΠΏΠ΅Ρ€Π΅Π΄Π°Π² Ρ‚ΡƒΠ΄Π° Π½Π°ΠΉΠ΄Π΅Π½Π½Ρ‹ΠΉ элСмСнт. Π­Ρ‚ΠΎ двухступСнчатый процСсс, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ ΠΌΠΎΠΆΠ΅Ρ‚ ΠΏΠΎΠΊΠ°Π·Π°Ρ‚ΡŒΡΡ ΠΌΠ΅Π½Π΅Π΅ эффСктивным, Π½ΠΎ ΠΎΠ½ обСспСчиваСт Π²Ρ‹ΡΠΎΠΊΡƒΡŽ Ρ‚ΠΎΡ‡Π½ΠΎΡΡ‚ΡŒ поиска Π² спСцифичСских структурах Π΄Π°Π½Π½Ρ‹Ρ….

  • πŸ” Поиск выполняСтся быстро Π΄Π°ΠΆΠ΅ Π² Π±ΠΎΠ»ΡŒΡˆΠΈΡ… списках благодаря Π²Π½ΡƒΡ‚Ρ€Π΅Π½Π½Π΅ΠΉ ΠΎΠΏΡ‚ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ.
  • βš™οΈ МоТно ΠΈΡΠΊΠ°Ρ‚ΡŒ элСмСнты ΠΏΠΎ Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹ΠΌ ΠΏΡ€ΠΈΠ·Π½Π°ΠΊΠ°ΠΌ, Ρ‚Π°ΠΊΠΈΠΌ ΠΊΠ°ΠΊ ΠΏΠΎΠΌΠ΅Ρ‚ΠΊΠ° удалСния ΠΈΠ»ΠΈ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ°.
  • πŸ“‰ ΠŸΡ€ΠΈ частом ΠΎΠ±Ρ€Π°Ρ‰Π΅Π½ΠΈΠΈ ΠΊ индСксам Π»ΡƒΡ‡ΡˆΠ΅ ΠΊΡΡˆΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Ρ‹, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π½Π΅ Π²Ρ‹ΠΏΠΎΠ»Π½ΡΡ‚ΡŒ поиск ΠΏΠΎΠ²Ρ‚ΠΎΡ€Π½ΠΎ.

Π‘Π»Π΅Π΄ΡƒΠ΅Ρ‚ ΡƒΡ‡ΠΈΡ‚Ρ‹Π²Π°Ρ‚ΡŒ, Ρ‡Ρ‚ΠΎ БписокЗначСний Ρ…Ρ€Π°Π½ΠΈΡ‚ элСмСнты Π² Π²ΠΈΠ΄Π΅ ΠΎΠ±ΡŠΠ΅ΠΊΡ‚ΠΎΠ² ЭлСмСнтБпискаЗначСний. ΠŸΡ€ΡΠΌΠΎΠ΅ сравнСниС значСния ΠΈΠ· массива со Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ΠΌ ΠΈΠ· списка ΠΌΠΎΠΆΠ΅Ρ‚ привСсти ΠΊ ошибкС Ρ‚ΠΈΠΏΠΎΠ². ВсСгда ΠΎΠ±Ρ€Π°Ρ‰Π°ΠΉΡ‚Π΅ΡΡŒ ΠΊ свойству Π—Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ элСмСнта списка ΠΏΡ€ΠΈ сравнСнии с внСшними Π΄Π°Π½Π½Ρ‹ΠΌΠΈ.

πŸ’‘

Если Π²Ρ‹ часто ΠΈΡ‰Π΅Ρ‚Π΅ элСмСнты Π² большом БпискСЗначСний, рассмотритС Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ использования индСкса ΠΈΠ»ΠΈ Π²ΡΠΏΠΎΠΌΠΎΠ³Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΠ³ΠΎ соотвСтствия для ускорСния доступа ΠΊ Π΄Π°Π½Π½Ρ‹ΠΌ.

Π‘Ρ€Π°Π²Π½Π΅Π½ΠΈΠ΅ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠ² поиска

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

НиТС ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Π° ΡΡ€Π°Π²Π½ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ Ρ‚Π°Π±Π»ΠΈΡ†Π°, Π΄Π΅ΠΌΠΎΠ½ΡΡ‚Ρ€ΠΈΡ€ΡƒΡŽΡ‰Π°Ρ ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π½ΠΎΠ΅ врСмя выполнСния ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΉ для массива ΠΈΠ· 10 000 элСмСнтов Π² Ρ‚ΠΈΠΏΠΈΡ‡Π½Ρ‹Ρ… условиях. Π”Π°Π½Π½Ρ‹Π΅ ΠΌΠΎΠ³ΡƒΡ‚ Π²Π°Ρ€ΡŒΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒΡΡ Π² зависимости ΠΎΡ‚ сСрвСрной инфраструктуры ΠΈ Π·Π°Π³Ρ€ΡƒΠ·ΠΊΠΈ систСмы.

ΠœΠ΅Ρ‚ΠΎΠ΄ поиска Π‘Ρ€Π΅Π΄Π½Π΅Π΅ врСмя (мс) Π‘Π»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π§ΠΈΡ‚Π°Π΅ΠΌΠΎΡΡ‚ΡŒ
ΠΠ°ΠΉΡ‚ΠΈΠ˜Π½Π΄Π΅ΠΊΡ (встроСнный) 2-5 Низкая Высокая
Π¦ΠΈΠΊΠ» "Для" (Ρ€ΡƒΡ‡Π½ΠΎΠΉ) 10-25 БрСдняя БрСдняя
Π¦ΠΈΠΊΠ» "Пока" с условиСм 15-30 Высокая Низкая
Поиск Π² БпискСЗначСний 5-10 БрСдняя Высокая

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

⚠️ Π’Π½ΠΈΠΌΠ°Π½ΠΈΠ΅: ΠŸΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ ΠΌΠΎΠΆΠ΅Ρ‚ сильно Π·Π°Π²ΠΈΡΠ΅Ρ‚ΡŒ ΠΎΡ‚ Ρ‚ΠΈΠΏΠ° Ρ…Ρ€Π°Π½ΠΈΠΌΡ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…. Поиск ΠΏΠΎ строкам с ΡƒΡ‡Π΅Ρ‚ΠΎΠΌ рСгистра Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ ΠΌΠ΅Π΄Π»Π΅Π½Π½Π΅Π΅, Ρ‡Π΅ΠΌ поиск ΠΏΠΎ числам ΠΈΠ»ΠΈ ссылкам. Π˜Π·Π±Π΅Π³Π°ΠΉΡ‚Π΅ Π»ΠΈΡˆΠ½ΠΈΡ… ΠΏΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΠΎΠ²Π°Π½ΠΈΠΉ Ρ‚ΠΈΠΏΠΎΠ² Π²Π½ΡƒΡ‚Ρ€ΠΈ Ρ†ΠΈΠΊΠ»ΠΎΠ² поиска.

ΠžΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ° ошибок ΠΈ ΠΎΡ‚ΡΡƒΡ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΡ… элСмСнтов

ΠšΠΎΡ€Ρ€Π΅ΠΊΡ‚Π½Π°Ρ ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ° ситуации, ΠΊΠΎΠ³Π΄Π° искомый элСмСнт Π½Π΅ Π½Π°ΠΉΠ΄Π΅Π½, являСтся ΠΏΡ€ΠΈΠ·Π½Π°ΠΊΠΎΠΌ качСствСнного ΠΊΠΎΠ΄Π°. ΠŸΠΎΠΏΡ‹Ρ‚ΠΊΠ° ΠΎΠ±Ρ€Π°Ρ‚ΠΈΡ‚ΡŒΡΡ ΠΊ массиву ΠΏΠΎ Π½Π΅ΡΡƒΡ‰Π΅ΡΡ‚Π²ΡƒΡŽΡ‰Π΅ΠΌΡƒ индСксу ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Ρ‚ ΠΊ возникновСнию ΠΈΡΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΡ Π˜Π½Π΄Π΅ΠΊΡΠ—Π°Π“Ρ€Π°Π½ΠΈΡ†Π΅ΠΉ, Ρ‡Ρ‚ΠΎ ΠΌΠΎΠΆΠ΅Ρ‚ ΠΏΡ€Π΅Ρ€Π²Π°Ρ‚ΡŒ Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ всСй Ρ‚Ρ€Π°Π½Π·Π°ΠΊΡ†ΠΈΠΈ. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΊΠ° Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π° поиска ΠΎΠ±ΡΠ·Π°Ρ‚Π΅Π»ΡŒΠ½Π° ΠΏΠ΅Ρ€Π΅Π΄ Π»ΡŽΠ±Ρ‹ΠΌ ΠΎΠ±Ρ€Π°Ρ‰Π΅Π½ΠΈΠ΅ΠΌ ΠΊ элСмСнту.

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

ИспользованиС конструкции ΠŸΠΎΠΏΡ‹Ρ‚ΠΊΠ°...Π˜ΡΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΠ΅ для ΠΏΠ΅Ρ€Π΅Ρ…Π²Π°Ρ‚Π° ошибки доступа ΠΏΠΎ индСксу считаСтся ΠΏΠ»ΠΎΡ…ΠΈΠΌ Ρ‚ΠΎΠ½ΠΎΠΌ Π² Π΄Π°Π½Π½ΠΎΠΌ контСкстС. Π˜ΡΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΡ Π΄ΠΎΠ»ΠΆΠ½Ρ‹ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒΡΡ для ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ Π°Π²Π°Ρ€ΠΈΠΉΠ½Ρ‹Ρ… ситуаций, Π° Π½Π΅ для управлСния ΠΏΠΎΡ‚ΠΎΠΊΠΎΠΌ выполнСния ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ ΠΏΡ€ΠΈ ΡˆΡ‚Π°Ρ‚Π½ΠΎΠΌ отсутствии Π΄Π°Π½Π½Ρ‹Ρ…. Π­Ρ‚ΠΎ Π½Π΅Π³Π°Ρ‚ΠΈΠ²Π½ΠΎ сказываСтся Π½Π° ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ ΠΈ услоТняСт ΠΎΡ‚Π»Π°Π΄ΠΊΡƒ.

ΠŸΠΎΡ‡Π΅ΠΌΡƒ Π½Π΅ стоит ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ Π˜ΡΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΡ для поиска?

ΠœΠ΅Ρ…Π°Π½ΠΈΠ·ΠΌ ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ ΠΈΡΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΠΉ Π² 1Π‘ рСсурсоСмкий. ГСнСрация ΠΎΠ±ΡŠΠ΅ΠΊΡ‚Π° ΠΈΡΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΡ, Π·Π°ΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ стСка Π²Ρ‹Π·ΠΎΠ²ΠΎΠ² ΠΈ ΠΏΠ΅Ρ€Π΅Π΄Π°Ρ‡Π° управлСния Ρ‚Ρ€Π΅Π±ΡƒΡŽΡ‚ Π·Π½Π°Ρ‡ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ большС Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ, Ρ‡Π΅ΠΌ простая ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΊΠ° условия 'Если ИндСкс = -1'. Π’ Ρ†ΠΈΠΊΠ»Π°Ρ… это ΠΌΠΎΠΆΠ΅Ρ‚ Π·Π°ΠΌΠ΅Π΄Π»ΠΈΡ‚ΡŒ Ρ€Π°Π±ΠΎΡ‚Ρƒ Π² дСсятки Ρ€Π°Π·.

ΠŸΡ€ΠΎΠ΄Π²ΠΈΠ½ΡƒΡ‚Ρ‹Π΅ Ρ‚Π΅Ρ…Π½ΠΈΠΊΠΈ ΠΈ оптимизация

Для Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊΠΎΠ², Ρ€Π°Π±ΠΎΡ‚Π°ΡŽΡ‰ΠΈΡ… с высоконагруТСнными систСмами, ΡΡƒΡ‰Π΅ΡΡ‚Π²ΡƒΡŽΡ‚ Π±ΠΎΠ»Π΅Π΅ слоТныС Ρ‚Π΅Ρ…Π½ΠΈΠΊΠΈ ΠΎΠΏΡ‚ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ поиска. Если массив отсортирован, ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡ€ΠΈΠΌΠ΅Π½ΠΈΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Π±ΠΈΠ½Π°Ρ€Π½ΠΎΠ³ΠΎ поиска, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ сокращаСт количСство ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΎΠΊ с Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠΉ зависимости Π΄ΠΎ логарифмичСской. Π₯отя Π² 1Π‘ Π½Π΅Ρ‚ встроСнной Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Π±ΠΈΠ½Π°Ρ€Π½ΠΎΠ³ΠΎ поиска для ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ»ΡŒΠ½Ρ‹Ρ… массивов, Π΅Π³ΠΎ Π»Π΅Π³ΠΊΠΎ Ρ€Π΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Ρ‚ΡŒ Π²Ρ€ΡƒΡ‡Π½ΡƒΡŽ.

Π•Ρ‰Π΅ ΠΎΠ΄ΠΈΠ½ эффСктивный ΠΏΡ€ΠΈΠ΅ΠΌ β€” использованиС ΠΎΠ±ΡŠΠ΅ΠΊΡ‚Π° БоотвСтствиС (Map) Π² качСствС Π²ΡΠΏΠΎΠΌΠΎΠ³Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΠΉ структуры. Π’Ρ‹ ΠΌΠΎΠΆΠ΅Ρ‚Π΅ ΠΎΠ΄ΠΈΠ½ Ρ€Π°Π· ΠΏΡ€ΠΎΠΉΡ‚ΠΈ ΠΏΠΎ массиву ΠΈ Π·Π°ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ соотвСтствиС, Π³Π΄Π΅ ΠΊΠ»ΡŽΡ‡ΠΎΠΌ Π±ΡƒΠ΄Π΅Ρ‚ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ элСмСнта, Π° Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ΠΌ β€” Π΅Π³ΠΎ индСкс. ΠŸΠΎΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠ΅ поиски Π±ΡƒΠ΄ΡƒΡ‚ Π²Ρ‹ΠΏΠΎΠ»Π½ΡΡ‚ΡŒΡΡ ΠΌΠ³Π½ΠΎΠ²Π΅Π½Π½ΠΎ, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ доступ ΠΊ элСмСнту соотвСтствия происходит Π·Π° константноС врСмя.

  • πŸš€ Π‘ΠΈΠ½Π°Ρ€Π½Ρ‹ΠΉ поиск Ρ‚Ρ€Π΅Π±ΡƒΠ΅Ρ‚ ΠΏΡ€Π΅Π΄Π²Π°Ρ€ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠΉ сортировки массива, Ρ‡Ρ‚ΠΎ добавляСт Π½Π°ΠΊΠ»Π°Π΄Π½Ρ‹Π΅ расходы.
  • 🧩 БоотвСтствия ΠΈΠ΄Π΅Π°Π»ΡŒΠ½Ρ‹ для частых поисков ΠΏΠΎ ΡƒΠ½ΠΈΠΊΠ°Π»ΡŒΠ½Ρ‹ΠΌ ΠΊΠ»ΡŽΡ‡Π°ΠΌ.
  • πŸ’Ύ Π”ΠΎΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹Π΅ структуры Π΄Π°Π½Π½Ρ‹Ρ… ΠΏΠΎΡ‚Ρ€Π΅Π±Π»ΡΡŽΡ‚ большС ΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΈΠ²Π½ΠΎΠΉ памяти.

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

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

Π’Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ΠΎ: 0 / 5
МоТно Π»ΠΈ Π½Π°ΠΉΡ‚ΠΈ индСкс элСмСнта Π² фиксированном массивС?

Π”Π°, ΠΌΠ΅Ρ‚ΠΎΠ΄Ρ‹ поиска Ρ€Π°Π±ΠΎΡ‚Π°ΡŽΡ‚ Π°Π½Π°Π»ΠΎΠ³ΠΈΡ‡Π½ΠΎ ΠΎΠ±Ρ‹Ρ‡Π½Ρ‹ΠΌ массивам. Однако ΠΏΠΎΠΌΠ½ΠΈΡ‚Π΅, Ρ‡Ρ‚ΠΎ фиксированный массив нСльзя ΠΈΠ·ΠΌΠ΅Π½ΡΡ‚ΡŒ, поэтому Π²Ρ‹ Π½Π΅ смоТСтС Π΄ΠΎΠ±Π°Π²ΠΈΡ‚ΡŒ элСмСнт, Ссли ΠΎΠ½ Π½Π΅ Π½Π°ΠΉΠ΄Π΅Π½. ΠœΠ΅Ρ‚ΠΎΠ΄ ΠΠ°ΠΉΡ‚ΠΈΠ˜Π½Π΄Π΅ΠΊΡ доступСн ΠΈ для этой структуры Π΄Π°Π½Π½Ρ‹Ρ….

Π§Ρ‚ΠΎ Π²Π΅Ρ€Π½Π΅Ρ‚ ΠΌΠ΅Ρ‚ΠΎΠ΄ ΠΠ°ΠΉΡ‚ΠΈΠ˜Π½Π΄Π΅ΠΊΡ, Ссли Π² массивС нСсколько ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹Ρ… элСмСнтов?

ΠœΠ΅Ρ‚ΠΎΠ΄ Π²Π΅Ρ€Π½Π΅Ρ‚ индСкс ΠΏΠ΅Ρ€Π²ΠΎΠ³ΠΎ Π½Π°ΠΉΠ΄Π΅Π½Π½ΠΎΠ³ΠΎ элСмСнта, начиная поиск с Π½Π°Ρ‡Π°Π»Π° массива (индСкс 0). Если Π²Π°ΠΌ Π½ΡƒΠΆΠ½Ρ‹ индСксы всСх Π²Ρ…ΠΎΠΆΠ΄Π΅Π½ΠΈΠΉ, Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ Ρ†ΠΈΠΊΠ» ΠΈ ΡΠΎΡ…Ρ€Π°Π½ΡΡ‚ΡŒ всС подходящиС ΠΏΠΎΠ·ΠΈΡ†ΠΈΠΈ Π² ΠΎΡ‚Π΄Π΅Π»ΡŒΠ½Ρ‹ΠΉ список.

Как Π½Π°ΠΉΡ‚ΠΈ индСкс элСмСнта Π² массивС структур?

ΠŸΡ€ΡΠΌΠΎΠΉ поиск ΠΏΠΎ структурС ΠΊΠ°ΠΊ ΠΏΠΎ Π·Π½Π°Ρ‡Π΅Π½ΠΈΡŽ ΠΌΠΎΠΆΠ΅Ρ‚ Π½Π΅ ΡΡ€Π°Π±ΠΎΡ‚Π°Ρ‚ΡŒ, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ структуры ΡΡ€Π°Π²Π½ΠΈΠ²Π°ΡŽΡ‚ΡΡ ΠΏΠΎ ссылкС. НСобходимо ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ Ρ†ΠΈΠΊΠ» ΠΈ ΡΡ€Π°Π²Π½ΠΈΠ²Π°Ρ‚ΡŒ ΠΊΠΎΠ½ΠΊΡ€Π΅Ρ‚Π½Ρ‹Π΅ ΠΊΠ»ΡŽΡ‡ΠΈ Π²Π½ΡƒΡ‚Ρ€ΠΈ структур, Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€: Если Π­Π»Π΅ΠΌΠ΅Π½Ρ‚.ΠšΠ»ΡŽΡ‡ = Π˜ΡΠΊΠΎΠΌΠΎΠ΅Π—Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Π’ΠΎΠ³Π΄Π°.

ВлияСт Π»ΠΈ Ρ‚ΠΈΠΏ сравнСния (строгоС/нСстрогоС) Π½Π° поиск?

Π’ 1Π‘ ΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΎΡ€ сравнСния = выполняСт строгоС сравнСниС с ΡƒΡ‡Π΅Ρ‚ΠΎΠΌ Ρ‚ΠΈΠΏΠΎΠ². Число 1 Π½Π΅ Ρ€Π°Π²Π½ΠΎ строкС "1". Для нСстрогого поиска Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ явно ΠΏΡ€ΠΈΠ²ΠΎΠ΄ΠΈΡ‚ΡŒ Ρ‚ΠΈΠΏΡ‹ Π΄Π°Π½Π½Ρ‹Ρ… ΠΏΠ΅Ρ€Π΅Π΄ сравнСниСм Π²Π½ΡƒΡ‚Ρ€ΠΈ Ρ†ΠΈΠΊΠ»Π°.

Π•ΡΡ‚ΡŒ Π»ΠΈ Ρ€Π°Π·Π½ΠΈΡ†Π° Π² поискС для массива Π½Π° ΠΊΠ»ΠΈΠ΅Π½Ρ‚Π΅ ΠΈ Π½Π° сСрвСрС?

Π›ΠΎΠ³ΠΈΠΊΠ° Ρ€Π°Π±ΠΎΡ‚Ρ‹ ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠ² ΠΈΠ΄Π΅Π½Ρ‚ΠΈΡ‡Π½Π°, Π½ΠΎ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ ΠΌΠΎΠΆΠ΅Ρ‚ ΠΎΡ‚Π»ΠΈΡ‡Π°Ρ‚ΡŒΡΡ ΠΈΠ·-Π·Π° Ρ€Π°Π·Π»ΠΈΡ‡ΠΈΠΉ Π² исполняСмой срСдС. На сСрвСрС ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ с большими массивами Π²Ρ‹ΠΏΠΎΠ»Π½ΡΡŽΡ‚ΡΡ ΡΡ‚Π°Π±ΠΈΠ»ΡŒΠ½Π΅Π΅. Π˜Π·Π±Π΅Π³Π°ΠΉΡ‚Π΅ ΠΏΠ΅Ρ€Π΅Π΄Π°Ρ‡ΠΈ Π±ΠΎΠ»ΡŒΡˆΠΈΡ… массивов с сСрвСра Π½Π° ΠΊΠ»ΠΈΠ΅Π½Ρ‚ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ для поиска индСкса β€” Π»ΡƒΡ‡ΡˆΠ΅ Π²Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ поиск Π½Π° сСрвСрС ΠΈ ΠΏΠ΅Ρ€Π΅Π΄Π°Ρ‚ΡŒ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚.