Телефонная книга: подскажите алгоритм быстрого поиска контактов

@Lafuzzer · Регистрация: 05.09.2014

Студворк — интернет-сервис помощи студентам

привет всем! какой самый быстрий алгоритм поиска контактов.и какие вы предлагайте
допустим у нас имена
Anton
Aren
Arsen
Arkadi
Baren
Vigen
если вводит А это понятно можно сделать маппами или интерполярний поиск,ну проблема потом когда вводит вторую потом третьую букву как это сделат! короче как у нас в мобилках контакты работают вот такой алгоритм надо

@FiLF · 05.09.2014, 00:49

Контакты можно хранить в дереве.

@Dani · 05.09.2014, 00:54

Сообщение от Lafuzzer

самый быстрий алгоритм поиска контактов

можно применить двоичный поиск если данные будут храниться в контейнерах, поддерживающих операцию индексирования

@Lafuzzer · 05.09.2014, 00:55 **[ТС]**

а каким образом именно искать?мап и сет само по себе механизм деревья!как сделать алгоритм поиска по буквам?

@Dani · 05.09.2014, 00:57

Можно использовать std::find с предикатом, который проверяет на соответствие нужной строки (набора первых букв) с префиксом проверяемой строки

@Lafuzzer · 05.09.2014, 01:00 **[ТС]**

а какая сложность у std::find?мне нужен самый эфективний способ!

@Dani · 05.09.2014, 01:08

O(N*K), где N - кол-во строк, K - максимальная длина строки.
Можно сделать за O(N) сделать. Только это на ночь я не объясню

@gazlan · 05.09.2014, 01:49

Сообщение от Lafuzzer

как у нас в мобилках

Trie, Ternary search tree

Discuss and implement phone book
Is it possible to efficiently store all possible phone numbers in memory?

+

Trie Data Structure in Java - Phone Book Application
Phone Directory Implementation Using TRIE (C#)

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .	SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .

@Lafuzzer 0 / 0 / 0 Регистрация: 05.09.2014 Сообщений: 4

	Телефонная книга: подскажите алгоритм быстрого поиска контактов 05.09.2014, 00:31. Показов 3163. Ответов 7 Метки нет (Все метки) привет всем! какой самый быстрий алгоритм поиска контактов.и какие вы предлагайте допустим у нас имена Anton Aren Arsen Arkadi Baren Vigen если вводит А это понятно можно сделать маппами или интерполярний поиск,ну проблема потом когда вводит вторую потом третьую букву как это сделат! короче как у нас в мобилках контакты работают вот такой алгоритм надо 0

@FiLF 54 / 54 / 37 Регистрация: 05.09.2013 Сообщений: 1,864
	05.09.2014, 00:49
	Контакты можно хранить в дереве. 0

@Lafuzzer 0 / 0 / 0 Регистрация: 05.09.2014 Сообщений: 4
	05.09.2014, 00:55 [ТС]
	а каким образом именно искать?мап и сет само по себе механизм деревья!как сделать алгоритм поиска по буквам? 0

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	05.09.2014, 00:57
	Можно использовать std::find с предикатом, который проверяет на соответствие нужной строки (набора первых букв) с префиксом проверяемой строки 0

@Lafuzzer 0 / 0 / 0 Регистрация: 05.09.2014 Сообщений: 4
	05.09.2014, 01:00 [ТС]
	а какая сложность у std::find?мне нужен самый эфективний способ! 0

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	05.09.2014, 01:08
	O(N*K), где N - кол-во строк, K - максимальная длина строки. Можно сделать за O(N) сделать. Только это на ночь я не объясню 0