Binary Search - Koresamuel

Binary search is applied to an ordered dataset, and its search algorithm is somewhat similar to the divide and conquer approach. Each time, it compares the middle element of the interval with the target element, narrowing down the search range by half until the desired element is found or the interval is reduced to zero.

Simple Binary Search#

/**
 *
 * @param {Array} array Ordered array
 * @param {Number} length Array length
 * @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 Array length
 * @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 occurrence of a given value#

/**
 *
 * @param {Array} array Ordered array
 * @param {Number} length Array length
 * @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 occurrence of a given value#

/**
 *
 * @param {Array} array Ordered array
 * @param {Number} length Array length
 * @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 value greater than or equal to a given value#

/**
 *
 * @param {Array} array Ordered array
 * @param {Number} length Array length
 * @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 value less than or equal to a given value#

/**
 *
 * @param {Array} array Ordered array
 * @param {Number} length Array length
 * @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;
}