Есть массив:
var arr = ['3','12','43','55','63','90'];
И есть какое-то число, допустим 13
Требуется найти такой индекс в массиве, чтобы элемент, на который он ссылается, был наибольшим из существующих элементов, которые меньше или равны заданному.
К примеру:
13 больше 12 (arr[1]), но меньше 43 (arr[2]), значит метод должен вернуть индекс 1 (вторая позиция)
Какими путями это можно реализовать?
Ответ
Собственно, если Ваш массив отсортированный, то Вам поможет старый добрый бинарный поиск, реализованный следующим образом:
function binSearch(arr, toFind) {
if (!arr) return -1;
var first = 0;
var last = arr.length - 1;
while (first < last) {
var mid = first + Math.floor((last - first) / 2);
if (arr[mid] >= toFind) last = mid;
else first = mid + 1;
}
if (arr[last] == toFind || last == 0 || last == arr.length - 1)
return last;
else
return last - 1;
}
console.log(binSearch(['3', '12', '43', '55', '63', '90'], 13)); // 1
Надеюсь, ответ помог Вам, удачи в Ваших делах!
Комментариев нет:
Отправить комментарий