Добрый всем день!
Мне нужно найти список всех городов подходящих по критерию поиска в строке.
Файл со списком городов приходит мне в json в таком формате
[
{
"Спорная территория": "",
"Область": "Алтайский край",
"Город": "Камень-на-Оби"
},
...
]
Я решил что эту проблему лучше всего решить с помощью бинарного поиска, так как список населенных пунктов довольно таки большой. Естественно для начала я сортирую весь приходящий массив по алфавиту по полю "Город", так как по этому полю и происходит поиск
const sortCities = () => citiesList.sort((a, b) => {
const nameA = a["Город"].toLowerCase();
const nameB = b["Город"].toLowerCase();
if (nameA < nameB) {
return -1
}
if (nameA > nameB) {
return 1
}
return 0
})
Далее, при вводе происходит поиск
const binarySearch = (list: ICities[], value: string): ICities[] => {
let suitableValues = []
let low = 0
let high = list.length - 1
while (low <= high) {
let mid = Math.floor((low + high) / 2)
let guess = list[mid]
let flag = true
for (let i = 0; i < value.length; i ++) {
if (guess["Город"].toLocaleLowerCase()[i] !== value.toLocaleLowerCase()[i]) {
flag = false
}
}
if (flag) {
suitableValues.push(guess)
}
if (guess["Город"].toLowerCase() > value.toLowerCase()) {
high = mid - 1
} else {
low = mid + 1
}
}
return suitableValues
}
Проблема в том, при выполнении условия flag - while не останавливается, а меняет значение low или high, что обрезает нужные мне значения. Я понимаю, что мне нужно прописать continue - но перед эти явно нужно какое-то изменение, чтобы не создавать бесконечный цикл, но не могу догадаться какое именно.
