Binary Search - Koresamuel

Binary search is targeted at an ordered data set, and its search algorithm is somewhat similar to the divide and conquer approach. Each time, it compares with the middle element of the interval to narrow down the search range by half until the desired element is found or the interval is reduced to 0.

Simple Binary Search#

/**
 *
 * @param {Array} array Ordered array
 * @param {Number} length Length of the array
 * @param {Number} value Value to search for
 * @returns Position
 */
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;
}

Recursive Binary Search#

/**
 *
 * @param {Array} array Ordered array
 * @param {Number} length Length of the array
 * @param {Number} value Value to search for
 * @returns Position
 */
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);
  }
}

Common Variations of Binary Search#

Variation 1: Find the first element equal to the given value#

/**
 *
 * @param {Array} array Ordered array
 * @param {Number} length Length of the array
 * @param {Number} value Value to search for
 * @returns Position
 */
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;
}

Variation 2: Find the last element equal to the given value#

/**
 *
 * @param {Array} array Ordered array
 * @param {Number} length Length of the array
 * @param {Number} value Value to search for
 * @returns Position
 */
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;
}

Variation 3: Find the first element greater than or equal to the given value#

/**
 *
 * @param {Array} array Ordered array
 * @param {Number} length Length of the array
 * @param {Number} value Value to search for
 * @returns Position
 */
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;
}

Variation 4: Find the last element less than or equal to the given value#

/**
 *
 * @param {Array} array Ordered array
 * @param {Number} length Length of the array
 * @param {Number} value Value to search for
 * @returns Position
 */
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;
}