二分查找变形问题实现

/*
 * @Description: 二分查找变形问题
 * @Author: Alisa
 * @Date: 2020-08-02 21:46:51
 * @LastEditors: Alisa
 * @LastEditTime: 2020-08-06 22:41:35
 */

/**
 * @description: 查找第一个等于待查找值的元素下标
 * @param {Array} arr 给定的数组
 * @param {Number} target 待查找的元素
 * @returns {Number} 查找到的元素下标
 */
function binarySearch1(arr, target) {
    let low = 0,
        high = arr.length - 1;
    while (low <= high) {
        let mid = parseInt(low + (high - low) / 2);
        if (arr[mid] > target) {
            high = mid - 1;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            if (mid === 0 || arr[mid - 1] !== target) {
                return mid;
            }
            high = mid - 1;
        }
    }
    return -1;
}

console.log(binarySearch1([1, 2, 4, 5, 7, 7, 9, 9, 11], 7));


/**
 * @description: 查找最后一个等于待查找值的元素下标
 * @param {Array} arr 给定的数组
 * @param {Number} target 待查找的元素
 * @returns {Number} 查找到的元素下标
 */
function binarySearch2(arr, target) {
    let low = 0,
        high = arr.length - 1;
    while (low <= high) {
        let mid = parseInt(low + (high - low) / 2);
        if (arr[mid] > target) {
            high = mid - 1;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            if (mid === arr.length - 1 || arr[mid + 1] !== target) {
                return mid;
            }
            low = mid + 1;
        }
    }
    return -1;
}

console.log(binarySearch2([1, 2, 4, 5, 7, 7, 9, 9, 11], 7));


/**
 * @description: 查找第一个不小于给定值的元素下标
 * @param {Array} arr 给定的数组
 * @param {Number} target 待查找的元素
 * @returns {Number} 查找到的元素下标
 */
function binarySearch3(arr, target) {
    let low = 0,
        high = arr.length - 1;
    while (low <= high) {
        let mid = parseInt(low + (high - low) / 2);
        if (arr[mid] >= target) {
            if (mid === 0 || arr[mid - 1] < target) {
                return mid;
            } else {
                high = mid - 1;
            }
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

console.log(binarySearch3([1, 2, 4, 5, 7, 7, 9, 9, 11], 1));


/**
 * @description: 查找最后一个不大于给定值的元素下标
 * @param {Array} arr 给定的数组
 * @param {Number} target 待查找的元素
 * @returns {Number} 查找到的元素下标
 */
function binarySearch4(arr, target) {
    let low = 0,
        high = arr.length - 1;
    while (low <= high) {
        let mid = parseInt(low + (high - low) / 2);
        if (arr[mid] <= target) {
            if (mid === arr.length - 1 || arr[mid + 1] > target) {
                return mid;
            } else {
                low = mid + 1;
            }
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

console.log(binarySearch4([1, 2, 4, 5, 7, 7, 9, 9, 11], 8));