二分查找的三种实现方式

/**
 * @description : 二分查找，正常查找
 * @return  {*} 找到返回该位置，找不到返回-1
 * @param {*} arr 传入的数组
 * @param {*} val 要查找的值
 */
let binarySearch = function (arr, val) {
    if (arr.length === 0) {
        return -1;
    }
    let left = 0;
    let right = arr.length - 1;
    while (left <= right) {
        let mid = left + Math.floor((right - left) / 2);
        if (arr[mid] == val) {
            return mid;
        } else if (arr[mid] < val) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
};
/**
 * @description : 二分查找，左侧区间，[0,arr.length)
 * 子区间：[left,mid)  [mid+1,right)
 * @return  {*} 返回left，就是查找的最左位置，找不到返回0
 * @param {*} arr
 * @param {*} val
 */
let binarySearchLeft = function (arr, val) {
    if (arr.length === 0) {
        return -1;
    }
    let left = 0;
    let right = arr.length;
    while (left < right) {
        let mid = left + Math.floor((right - left) / 2);
        if (arr[mid] < val) {
            left = mid + 1;
        } else if (arr[mid] > val) {
            right = mid;
        } else if (arr[mid] == val) {
            right = mid;
        }
    }
    return left;
}
/**
 * @description : 二分查找，右侧区间，[0,arr.length)
 * 子区间：[left,mid)  [mid+1,right)
 * @return  {*} 返回left-1，就是查找的最右位置，找不到返回0
 * @param {*} arr
 * @param {*} val
 */
let binarySearchRight = function (arr, val) {
    if (arr.length === 0) {
        return -1;
    }
    let left = 0;
    let right = arr.length;
    while (left < right) {
        let mid = left + Math.floor((right - left) / 2);
        if (arr[mid] <= val) {
            left = mid + 1;
        } else if (arr[mid] > val) {
            right = mid;
        } else if (arr[mid] == val) {
            left = mid + 1;
        }
    }
    return left - 1;
}
let arr = [1, 5, 8, 9, 9, 9, 9, 11];
let res = binarySearch(arr, 9);
let res2 = binarySearchLeft(arr, 9);
let res3 = binarySearchRight(arr, 9);
console.log(res);  // 3
console.log(res2);  // 3
console.log(res3);  // 6

吃香蕉

在JS中(right - left) / 2得到的可以是小数，这与Java中不同，因此要Math.floor(……)

/**
 * @param {number[]} piles
 * @param {number} h
 * @return {number}
 */
var minEatingSpeed = function (piles, H) {
    let left = 1, right = getMax(piles) + 1;
    while (left < right) {
        let mid = left + Math.floor((right - left) / 2);
        if (canFinish(piles, mid, H)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
};
let getMax = function (piles) {
    let max = 0;
    for (const n of piles) {
        max = Math.max(n, max);
    }
    return max;
}
let timeOf = function (n, speed) {
    return Math.floor(n / speed) + ((n % speed > 0) ? 1 : 0);
}
let canFinish = function (piles, speed, H) {
    let time = 0;
    for (const n of piles) {
        time += timeOf(n, speed);
    }
    return time <= H;
}

运包裹

/**
 * @param {number[]} weights
 * @param {number} D
 * @return {number}
 */
var shipWithinDays = function (weights, D) {
    let low = maxDays(weights);
    let high = sum(weights) + 1;
    while (low < high) {
        let mid = low + Math.floor((high - low) / 2);
        if (canFinish(weights, D, mid)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low - 1;
};
let canFinish = function (weights, D, carry) {
    let j = 0;
    for (let i = 0; i < D; i++) {
        let cap = carry;
        while (weights[j] < cap) {
            cap = cap - weights[j];
            j++;
        }
    }
    if (j == weights.length) {
        return true;
    } else {
        return false;
    }
}
let sum = function (weights) {
    let sum = 0;
    for (let w of weights) {
        sum = sum + w;
    }
    return sum;
}
let maxDays = function (weights) {
    let max = -Infinity;
    for (let w of weights) {
        if (w > max) {
            max = w;
        }
    }
    return max;
}