Как лучше реализовать такую задачу?

При автодополнении можно возвращать все совпадения по названию и уточнение в виде страны в скобках. Это не сильно проблемно.

@BloodyHistory это не проблема но лишний геморой.

не используйте id в селекторах...

используйте id в селекторах...

@DonSinDRom, аргументируйте. Скажем мои аргументы:
id элемента должно быть уникальным на странице, что делает js код завязанный на id-шники ужасно неповоротливым (в большинстве случаев) и плохо расширяемым. повышает дублирование и все такое прочее. Это уже не говоря о том что в один прекрасный момент именно из-за нежелания менять js логику разработчик добавляет на страницу другой элемент с тем же id. Я за декларативный подход с селекторами завязанными на специфичные классы а лучше data-* атрибуты. Аргументы же типа "селекторы по id быстрее" смешны.

используйте id в этом селекторе.

@Fesor в данном случае требуется привязка именно к id, поскольку случайное появление элемента с аналогичным селектором (класс, ...) на странице вызовет нежелательные эффекты.

@metamorph Техническая сторона также интересна...

@eprivalov
Вариант 1: воспользоваться готовым решением (ссылки есть выше в ответах)

Вариант 2: найдите базу стран-регионов-городов. Сделайте к ней ajax-интерфейс, который по названию будет отдавать данные по городам. К примеру:
select c.id, c.name, r.name, k.name from cities c left join regions r on c.region_id = r.id left join countries k on c.country_id = k.id order by ...
У некоторых городов мира нет привязки к региону, поэтому в region_id иногда будут встречаться null.

Ответ от сервера разгребайте и формируйте выпадающий список с указанием региона и страны, типа
МО
МОСКВА, Россия, Московская обл.
МОЖАЙСК, Россия, Можайская обл.
МОГИЛЕВ, Белоруссия, Могилевская обл.

Самое интересное, полагаю, будет с order by. Тут, наверное, имеет смысл ввести понятие "вес", чтобы москва появлялась выше мохосранска. Хорошо бы еще учитывать текущее местоположение пользователя, чтобы еще и по стране сортировать.

@metamorph @eprivalov habrahabr.ru/post/21949 - думаю поможет.