二分查找 - Koresamuel

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

简单的二分查找#

/**
 *
 * @param {Array} array 有序数组
 * @param {Number} length 数组长度
 * @param {Number} value 查找的值
 * @returns 所在位置
 */
function bsearch(array, length, value) {
  let left = 0;
  let right = length - 1;
  while (left <= right) {
    let mid = (left + right) >> 1;
    if (array[mid] === value) {
      return mid;
    } else if (array[mid] < value) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

递归二分查找#

/**
 *
 * @param {Array} array 有序数组
 * @param {Number} length 数组长度
 * @param {Number} value 查找的值
 * @returns 所在位置
 */
function bsearch(array, length, value) {
  return bsearchInternal(array, 0, length - 1, value);
}

function bsearchInternal(array, left, right, value) {
  if (left > right) return -1;

  let mid = (left + right) >> 1;
  if (array[mid] === value) {
    return mid;
  } else if (array[mid] < value) {
    return bsearchInternal(array, mid + 1, right, value);
  } else {
    return bsearchInternal(array, left, mid - 1, value);
  }
}

常见二分查找变形问题#

变体一：查找第一个值等于给定值的元素#

/**
 *
 * @param {Array} array 有序数组
 * @param {Number} length 数组长度
 * @param {Number} value 查找的值
 * @returns 所在位置
 */
function bsearch(array, length, value) {
  let left = 0;
  let right = length - 1;

  while (left <= right) {
    let mid = (left + right) >> 1;
    if (array[mid] > value) {
      right = mid - 1;
    } else if (array[mid] < value) {
      left = mid + 1;
    } else {
      if (mid === 0 || (array[mid - 1] !== value)) {
        return mid
      } else {
        right = mid - 1;
      }
    }
  }

  return -1;
}

变体二：查找最后一个值等于给定值的元素#

/**
 *
 * @param {Array} array 有序数组
 * @param {Number} length 数组长度
 * @param {Number} value 查找的值
 * @returns 所在位置
 */
function bsearch(array, length, value) {
  let left = 0;
  let right = length - 1;

  while (left <= right) {
    let mid = (left + right) >> 1;
    if (array[mid] > value) {
      right = mid - 1;
    } else if (array[mid] < value) {
      left = mid + 1;
    } else {
      if ((array[mid + 1] !== value) || (mid === (length - 1))) {
        return mid;
      } else {
        left = mid + 1;
      }
    }
  }

  return -1;
}

变体三：查找第一个大于等于给定值的元素#

/**
 *
 * @param {Array} array 有序数组
 * @param {Number} length 数组长度
 * @param {Number} value 查找的值
 * @returns 所在位置
 */
function bsearch(array, length, value) {
  let left = 0;
  let right = length - 1;

  while (left <= right) {
    let mid = (left + right) >> 1;
    if (array[mid] >= value) {
      if ((array[mid - 1] < value) || (mid === 0)) {
        return mid;
      } else {
        right = mid - 1
      }
    } else {
      left = mid + 1;
    }
  }

  return -1;
}

变体四：查找最后一个小于等于给定值的元素#

/**
 *
 * @param {Array} array 有序数组
 * @param {Number} length 数组长度
 * @param {Number} value 查找的值
 * @returns 所在位置
 */
function bsearch(array, length, value) {
  let left = 0;
  let right = length - 1;

  while (left <= right) {
    let mid = (left + right) >> 1;
    if (array[mid] <= value) {
      if ((array[mid + 1] > value) || (mid === length - 1)) {
        return mid;
      } else {
        left = mid + 1
      }
    } else {
      right = mid - 1;
    }
  }

  return -1;
}