二分探索 - 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);
  }
}

よくある二分探索の変形問題#

変形 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 (mid === 0 || (array[mid - 1] !== value)) {
        return mid
      } else {
        right = mid - 1;
      }
    }
  }

  return -1;
}

変形 2：最後に与えられた値と等しい要素を探す#

/**
 *
 * @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;
}

変形 3：最初に与えられた値以上の要素を探す#

/**
 *
 * @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;
}

変形 4：最後に与えられた値以下の要素を探す#

/**
 *
 * @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;
}