| Вопрос: Узнать есть ли элемент в массиве без его переборки | Добавлено: 16.02.09 15:18 |
Автор вопроса:  Destroyer
|
|
Всем привет, собственно такой вопрос. Допустим есть массив array1 с содержимым
1 2 3 4 5 так вот, как можно правильней узнать есть ли "3" в этом массиве без его полной переборки и сравнения каждого элемента? или это единственный способ? |
| Ответы | Всего ответов: 35 |
|
Номер ответа: 1 Автор ответа:  EROS Вопросов: 58 Ответов: 4255  |
Профиль | | #1 | Добавлено: 16.02.09 15:43 |
| Если это чистый Array то только перебор, а если это ArrayList, то у него есть метод Contains .. хотя он наверняка тоже использует перебор за кулисами.. | ||
|
Номер ответа: 2 Автор ответа: fAndOrIn Вопросов: 5 Ответов: 344 |
Профиль | | #2 | Добавлено: 16.02.09 16:33 |
|
Как это помягче выразиться, чтоб никого не разозлить!
В большинстве случаев полной переборки можно избежать, используя Exit For (или как там на NET) при первом совпадении.
|
||
|
Номер ответа: 3 Автор ответа: БоцманICQ: 295725312 Вопросов: 53 Ответов: 830 |
Web-сайт: Профиль | | #3 | Добавлено: 16.02.09 16:57 |
|
fAndOrIn используй Exit For
все равно до тройки будешь перебирать, но ведь чел спросил образно? а мог бы и так, как можно правильней узнать есть ли "200000071". А массив всего например 200000073. Можно поизголятся в таком варианте, например масив равен 100 а поиск 39. То например если 100 \39 > 2 then поиск от 0 до 50 полтийника, если нет то от полтийника до рубля. В первом случае выгрыш отрицательный во втором абсолютен. |
||
|
Номер ответа: 4 Автор ответа: fAndOrInВопросов: 5 Ответов: 344 |
Профиль | | #4 | Добавлено: 16.02.09 17:06 |
| Ну вот, опять нарвался... Вроде не пятница,13? А из вышесказанного понял лишь то, что видимо предполагается, что массив возрастающий? Или ничего не понял. | ||
|
Номер ответа: 5 Автор ответа: fAndOrInВопросов: 5 Ответов: 344 |
Профиль | | #5 | Добавлено: 16.02.09 17:09 |
|
А для случая есть ли "200000071". А массив всего например 200000073 выигрыш хоть на 2 позиции, но есть!
|
||
|
Номер ответа: 6 Автор ответа: EROSВопросов: 58 Ответов: 4255 |
Профиль | | #6 | Добавлено: 16.02.09 17:09 |
|
Ну вот, опять нарвался...
старик, сегодня просто не твой день! 
|
||
|
Номер ответа: 7 Автор ответа: AgentFireICQ: 192496851 Вопросов: 75 Ответов: 3178 |
Профиль | | #7 | Добавлено: 16.02.09 17:11 |
|
Скорее всего возрастащий массив он привел как пример.
Еще не наскучило заниматься телепатией и гадать, что ИМЕННО нужно автору?  (эт если он сам знает)
|
||
|
Номер ответа: 8 Автор ответа: Destroyer Вопросов: 2 Ответов: 3 |
Профиль | | #8 | Добавлено: 16.02.09 18:09 |
|
Ну да, я образно пример привёл, в массиве уже есть данные, просто сверять их каждый раз полным перебором долго (если большой массив) и я подумал может есть более правильное решение. Массив обычный String'овый не ArrayList. Ведь если нужно найти "5" в моём примере, то придёться перебирать весь массив в поиске этого эллемента. Про Exit for это обязательно использую.
|
||
|
Номер ответа: 9 Автор ответа: fAndOrInВопросов: 5 Ответов: 344 |
Профиль | | #9 | Добавлено: 16.02.09 18:40 |
| В этом случае, скорее всего, какой-то оптимации поиска можно добиться, если массив отсортирован (если нет, может быть есть смысл его отсортировать http://www.vbnet.ru/forum/show.aspx?id=182195&page=2). Тогда может помочь метод половинного деления или еще там какой-нибудь. | ||
|
Номер ответа: 10 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #10 | Добавлено: 16.02.09 18:53 |
| Отсортируй и бинарным поиском. | ||
|
Номер ответа: 11 Автор ответа: Ra$calICQ: 8068014 Вопросов: 18 Ответов: 817 |
Web-сайт: Профиль | | #11 | Добавлено: 16.02.09 19:05 |
| если хочется совсем без перебора, то отказываешься от массива и используешь хэш таблицу. | ||
|
Номер ответа: 12 Автор ответа: fAndOrInВопросов: 5 Ответов: 344 |
Профиль | | #12 | Добавлено: 16.02.09 19:44 |
|
Чисто из любобытства и в целях повышения крутизны собственного кунг-фу осмелюсь поинтересоваться насчет бинарного поиска:
1 - поможет ли он в случае, если массив описан как A()as string, а не A()as string[C] 2 - не выдаст ли он положительный результат при поиске "cdef" в случае A(n)="abcd": A(n+1)="cdef". Простите за наивный, м.б. вопрос... и только не по почкам, плиззз! |
||
|
Номер ответа: 13 Автор ответа: ArtyomРазработчик Вопросов: 130 Ответов: 6602 |
Профиль | | #13 | Добавлено: 16.02.09 20:24 |
|
черт, Sharp опередил, вобщем я то же самое хотел сказать.
Если массив не отсортирован, то без "перебора" решить не получится, по крайней мере от начала списка до первого вхождения элемента. Если отсортирован, бинарным поиском, это очень быстро. |
||
|
Номер ответа: 14 Автор ответа: ArtyomРазработчик Вопросов: 130 Ответов: 6602 |
Профиль | | #14 | Добавлено: 16.02.09 20:35 |
|
1. A()as string[C]
А что значит String[C]? В VB .NET такого нет и не было никогда... 2. не выдаст ли он положительный результат при поиске "cdef" в случае A(n)="abcd": A(n+1)="cdef" Нет, не выдаст. |
||
|
Номер ответа: 15 Автор ответа: ArtyomРазработчик Вопросов: 130 Ответов: 6602 |
Профиль | | #15 | Добавлено: 16.02.09 20:48 |
|
Ra$cal пишет:
если хочется совсем без перебора, то отказываешься от массива и используешь хэш таблицу. Я бы все-таки хеш-таблицу использовать не стал... Хеш-таблица дает ощутимые накладные расходы на память (по сравнению с массивом требует примерно в 10 раз больше ОЗУ). Но зато по быстродействию, Dictionary быстрее BinarySearch примерно в 7.5 раз. Впрочем вряд ли эта разница будет играть роль, потому что на массиве из 10М элементов выигрыш перед IndexOf составляет более 100 тысяч раз
|
||