Skip to content
RSS feedtkhwang on GitHubtkhwang on Twitter

๐Ÿ”ฅ Binary search in javascript

Binary search concept seems to be easy, but it's quite difficult to apply to various problem.

  • Basic binary search
  • Binary search for duplicate elements
  • Generalized binary search to find min/max

โœจ I. Basic

  • Both inclusive ranges [left, right] are used.
  • Therefore = used in while condition in order to include for checking the same left and right case.
const bisect = (array, target) => {
  const N = array.length;

  // [left, right] : Both inclusive ranges
  let left = 0;
  let right = N - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (array[mid] === target) {
      return mid;
    } else if (array[mid] < target) {
      left = mid + 1;
    } else if (target < array[mid]) {
      right = mid - 1;
    }
  }
  // left is the insertion point
  return left;
};

โœจ II. Binary search for duplicate elements

  • The insertion point can be larger than the length of array.
  • Half inclusive ranges [left, right) are used.
    • left = 0
    • right = N
  • Search space is [left, right).
    • [left, left) is not valid region, so that while(left < right).

โœจ (II.1) left-most

  • We will find array[left] === target
  • left will be returned.
//         |
//        \/
//       target, target, target, other...
//       [left,  right)
//                          |
//                         \/
//             other..., target, other...
//                       [left, right)
// return left
  • If check is done in mid. The next space will be split into the followings.
    • [left, mid)
    • mid
    • [mid + 1, right).
const leftBound = (array, target, left = 0, right = array.length) => {
  // [left, right)

  while (left < right) {
    const mid = Math.floor((left + right) / 2);

    if (array[mid] === target) {
      right = mid;
    } else if (array[mid] < target) {
      left = mid + 1;
    } else if (array[mid] > target) {
      right = mid;
    }
  }
  // index
  return left;

  // check whether array[left] === target
  // if (left === array.length) return -1
  // return array[left] === target ? left : -1
};

๐Ÿ”ฅ [object Object] : simple version

  • If the mid value (array[mid]) is larger or equal to target (array[mid] >= target).
    • we observed that mid is array[mid] >= target.
    • so, we use this founding mid as right
    • and then, search for the left region to find whether this is smaller left
  • If the mid value (array[mid]) is smaller than target (array[mid] < target).
    • we observed that mid is array[mid] < target.
    • this mid can not be left because it's smaller than target.
    • we need larger value left = mid + 1.
    • next, search for the right region.
const leftBound = (array, target, left = 0, right = array.length) => {
  // [left, right)

  while (left < right) {
    const mid = Math.floor((left + right) / 2);

    if (array[mid] >= target) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  // index
  return left;

  // check whether array[left] === target
  // if (left === array.length) return -1
  // return array[left] === target ? left : -1
};

๐Ÿ”ฅ (II.2) right most point

  • We will find the minimum left such that array[left] > target.
//                                |
//                                \/
//       target, target, target, other...
//                               [left,  right]
//                                |
//                                \/
//             other..., target, other...
//                               [left,  right]
// return (left - 1)
  • Final left is the right-most insertion point which is NOT same as target.
const rightBound = (array, target, left = 0, right = array.length) => {
  // [left, right)

  while (left < right) {
    const mid = Math.floor((left + right) / 2);

    if (array[mid] === target) {
      left = mid + 1;
    } else if (array[mid] < target) {
      left = mid + 1;
    } else if (array[mid] > target) {
      right = mid;
    }
  }
  // right-most
  return left - 1;

  // check whether array[left-1] === target
  // if (left === 0) return -1;
  // return array[left-1] === target ? left -1 : -1
};

๐Ÿ”ฅ [object Object] : simple version

  • If the mid value (array[mid]) is larger than target (array[mid] > target).
    • we observed that mid is array[mid] > target.
    • mid can be right, so that we use this founding mid as right.
    • and then, search for the left region to find whether there is smaller left
  • If the mid value (array[mid]) is smaller or equal to target (array[mid] <= target).
    • we observed that mid is array[mid] <= target.
    • we are looking for the left which is larger than target.
    • this mid can not be left because it's smaller than target.
    • we need larger value left = mid + 1.
    • next, search for the right region.
  • Final left is the right-most insertion point.
  • If you need the largest maching location which is the same as the target, need to check whether array[left - 1] is target.
const rightBound = (array, target, left = 0, right = array.length) => {
  // [left, right) half inclusive range
  while (left < right) {
    const mid = Math.floor((left + right) / 2);

    // right-most
    if (array[mid] > target) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  // right-most
  return left - 1;

  // check whether array[left -1] === target
  // if (left === 0) return -1;
  // return array[left-1] === target ? left -1 : -1
};

๐Ÿ—’๏ธ Typical problems

  • Both inclusive ranges [left, right] are used.
  • Therefore = used in while condition in order to include for checking the same left and right case.

โœจ III.0 Understand the problem and find the monotonicity

  • The most difficult part.
  • Understand the problem and find which variable should be changed.
  • This variable must show the monotonicity feature, which makes it possible to find the minimum/maximum value by using binary search.

๐Ÿ”ฅ III.1 Find the minimum value

  • Find the minimum value using left pointer.
const check = (num) => {
  /*
           ------
           |
        ----
            <== true ==>
            [left, right]
   */
  return BOOLEAN;
};
  • If mid is in true region, search for smaller value [left, mid-1].
  • If mid is NOT in true region, search for larger value [mid + 1, right].
// [left, right] : Both inclusive ranges
let left = MINIMUM_POSSIBLE_ANSWER;
let right = MAXMIMUM_POSSIBLE_ANSWER;

while (left <= right) {
  const mid = Math.floor((left + right) / 2);

  if (check(mid)) {
    right = mid - 1;
  } else {
    left = mid + 1;
  }
  return left;
}

๐Ÿ”ฅ III.2 Find the maximum value

  • Find the maximum value using right pointer
const check = (num) => {
  /*
            -------
                  |
                  ------------
      <== true ==>
     [left, right]
   */
  return BOOLEN;
};
  • If mid is TRUE region, search for larger value [mid + 1, right].
  • If mid is NOT in TRUE region, search for smaller value [left, mid - 1].
// [left, right] : Both inclusive ranges
let left = MINIMUM_POSSIBLE_ANSWER;
let right = MAXMIMUM_POSSIBLE_ANSWER;

while (left <= right) {
  const mid = Math.floor((left + right) / 2);

  if (check(mid)) {
    left = mid + 1;
  } else {
    right = mid - 1;
  }
  return right;
}

๐Ÿ—’๏ธ Typical problems

List

๐Ÿ“š References