二分查找 - 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;
}