🔥 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.

🔥 I.1 basic binary search

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

• 34. Find First and Last Position of Element in Sorted Array - Leetcode

III. Generalized binary search

• 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;
}

🏷️ Related tags

• #binary-search

🗒️ Typical problems

List

• Binary Search - List by @sachin_ak

📚 References

• (premium) LICC (Leetcode's Interview Crash Course)
• The Only Lists You Need For Your Interview Preparation
• 我写了首诗，让你闭着眼睛也能写对二分搜索