Позиция элемента в отсортированном массиве

#javascript #jquery

Есть массив:

var arr = ['3','12','43','55','63','90'];


И есть какое-то число, допустим 13.

Требуется найти такой индекс в массиве, чтобы элемент, на который он ссылается, был
наибольшим из существующих элементов, которые меньше или равны заданному.

К примеру:
13 больше 12 (arr[1]), но меньше 43 (arr[2]), значит метод должен вернуть индекс
1 (вторая позиция)
Какими путями это можно реализовать?
    

Ответы

Ответ 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




Надеюсь, ответ помог Вам, удачи в Ваших делах!