binary-search-async-algo-week.md

Binary Search 🕵🕵️‍♂️

---

Interviewer Prompt

Write a function that takes in a sorted array of integers as well as a target value. The function should use the Binary Search Algorithm to determine if the target value is contained in the array and should return its index if it is, otherwise it should return -1.

---

Setup and Examples

You may provide your interviewee with these examples if you like. I would use replt for this one.

console.log(binarySearch([1, 2, 5, 7, 8, 9], 2)); // => 1
console.log(binarySearch([1, 2, 5, 7, 8, 9], 8)); // => 4
console.log(binarySearch([1, 2, 5, 7, 8, 9], 9)); // => 5
console.log(binarySearch([1, 2, 5, 7, 8, 9], 11)); // => -1
console.log(binarySearch([1, 2, 5, 7, 8, 9], -5)); // => -1

---

Interviewer Guide

---

RE

Example for interviewer comprehension:

• Consider the array [1, 3, 4, 7, 12, 17, 20]. We want to locate the index of 17. First compare 17 to the middle of the array, which is 7. Because 17 > 7 we then repeat the comparison using the subarray[12, 17, 20]. We find that 17 matches the middle of this array, and so we output the index from the original array, which is 5. Note that we do not output the index of 17 from the smaller subarray.

---

AC

You may need to walk your interviewee through what a binary search algorithm is:

• We first want to identify the middle number in the array. Next determine if the value to be found is greater than, lower than, or equal to the middle number. If it is equal, you are finished, and output the index of the found value. If not, repeat the procedure for a smaller array, this array is formed from by taking half of the given array that the specified number falls into.

---

TO

• If your interviewee finishes, ask them:
• What is the Big 0 of this problem? How does this problems time complexity compare to 0(n) and the problem we did yesteday?

---

SOLUTION 1

function binarySearch(arr, value){
    let left = 0
    let right = arr.length - 1;
  
   while(left <= right){
        let middle = Math.floor((right + left) / 2)
           if (arr[middle] === value){
                return middle 
            }
           if (arr[middle] < value){
               left = middle + 1;
            } else {
               right = middle - 1;
            }
        }
      return -1
   }

Big O

• Time Complexity: 0(log(n))
• Space Complexity: 0(1) constant

---

SOLUTION 2 - Introducing Helper Functions (the 1st solution is preferred)

function binarySearch(arr, value) {
  return helperFunction(arr, value, 0, arr.length-1)
}

function helperFunction(arr, value, start, end){
  if (start > end) return -1 

  let middle = Math.floor((start + end) / 2)
  let mayBeMatch = arr[middle]

  if (value === mayBeMatch) {
    return middle
  } else if (value < mayBeMatch){
    return helperFunction(arr, value, start, middle - 1)
  } else {
    return helperFunction(arr, value, middle + 1, end);
  }
}

Big O

• Time Complexity: 0(log(n))
• Space Complexity: 0(log(n))

---

Try it out yourself below 💁🏽‍♀️:

💻 Repl: https://repl.it/@kyvyCodes/Async-Algo-Day-2#index.js