11_binary-search

Binary search

When to use

whenever we are given a sorted Array or LinkedList or Matrix, and we are asked to find a certain element, the best algorithm we can use is the Binary Search.

Pseudo code

There are multiple ways to write binary search function, here I use the [start, end) style (the search range does not include end), this seems not correct at first, e.g. if arr[middle] === target, the loop still runs and the next step end = middle will bypass middle (because end is not included). However, start will keep approaching the correct middle when the loop goes on, and will finally stops at middle when loops end. This seems counter-intuitive at first, but the benefit here is the final start will be the correct position to insert the target even it's not existed in the original array. In addition, we can think the final start as the smallest index in the array which can make arr[middle] >= target true, i.e. the smallest index to make the "end change condition" true, this is very useful when we need to use the binary search to find the upper bound or lower bound for a target (e.g. 34_find-first-and-last-position-of-element-in-sorted-array).

function binarySearch1(sortedArr, target) {
  let start = 0;
  // end will not be included in the search range
  let end = sortedArr.length;
  while (start < end) {
    const middle = start + Math.floor((end - start) / 2);
    if (sortedArr[middle] >= target) {
      end = middle;
    } else {
      start = middle + 1;
    }
  }
  // start can be [0, sortedArr.length]
  // 1. need to check if it's out of range first
  // 2. need to check if start === target
  return start;
}

// traditional binary search
function binarySearch2(sortedArr, target) {
  let start = 0;
  // end will be included in the search range
  let end = sortedArr.length - 1;
  while (start <= end) {
    const middle = start + Math.floor((end - start) / 2);
    if (sortedArr[middle] === target) {
      return middle;
    }
    if (sortedArr[middle] > target) {
      end = middle - 1;
    } else {
      start = middle + 1;
    }
  }
  return -1;
}

Note1: sometimes the initial value of end (e.g. end = sortedArr.length - 1) and the while loop condition equality (e.g. while (start <= end)) can be confusing, when to use which? We can think about this question from this perspective:

• if we need to access sortedArr[end] in the loop, we need to make sure end is always a valid index, so the initial value of end should be sortedArr.length - 1. (e.g. 153_find-minimum-in-rotated-sorted-array)
• if we use end = middle or start = middle in the loop, which means for curtain scenarios we can't exclude middle index, then we can't use while (start <= end) because it will end up infinite loop.

Note2: for rotated sorted array (sorted array being rotated, the max number is sitting somewhere in the middle) related questions, it's always a good idea to compare middle with either start or end, because at least one section is sorted. (e.g. 153_find-minimum-in-rotated-sorted-arrayand 33_search-in-rotated-sorted-array)

Note3: for bitonic array (numbers are ascending first then descending), the typical strategy is to find its maximum index first via binary search, then we can split the array into 2 parts: [start, max] and [max, end], both of them are sorted array, the first array is in ascending order, the second one is in descending order. (check 162_bitonic-array-maximum and 0_search-bitonic-array for details.)