Binary search for closest value

binaryClosestSearch.js

/*!
    Бинарный поиск ближайшего значения. Если значение за пределами списка, возвращает индекс крайнего элемента.
    Возвращает индекс найденного элемента.

    x >> 1 === Math.floor(x / 2)

    \param type:array list
    \param type:number value
    \param type:function getVal функция, которая достает нужное значение из элемента списка list
    
    \returns type:number
*/
function binaryClosestSearch(list, value, getVal) {
    if (!getVal) {
        getVal = function(val) { return val; };
    }

    var start = 0;
    var end = list.length - 1;
    var mid = (end + start) >> 1;
    while (start < end && getVal(list[mid]) !== value) {
        if (value < getVal(list[mid])) {
            end = mid - 1;
        } else if (value > getVal(list[mid])) {
            start = mid + 1;
        }
        mid = (end + start) >> 1;
    }

    var result;
    if (getVal(list[mid]) === value) {
        result = mid;
    } else {
        // Точного совпадения не было, ищем ближайший к искомому элемент.
        var prev = mid - 1;
        var next = mid + 1;

        function diff(index) {
            return Math.abs(value - getVal(list[index]));
        }

        // Проверяем значения вокруг mid, если они есть, то будем сравнить разницу value с ними.
        // Если какого-то из них нет, то вместо него берем сам mid.
        if (prev < 0) {
            result = diff(mid) < diff(next) ? mid : next;
        } else if (next >= list.length) {
            result = diff(prev) < diff(mid) ? prev : mid;
        } else {
            // Если есть оба значения вокруг, то сравниваем разницу всех трех значений с value.
            if (diff(prev) < diff(mid)) {
                result = diff(prev) < diff(next) ? prev : next;
            } else {
                result = diff(mid) < diff(next) ? mid : next;
            }
        }
    }

    return result;
}