Binary Search

Q. Write an algorithm that performs binary search on a given array. The function will also track, and print out the number of steps required to reach the target of the index of the item.

let testArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 15, 16, 19, 24, 29, 39, 45]
const binarySearch = function(arr, target) {
 let index = 0;
 let middleIndex = 0;
 let newArr = arr;

 for (let i = 0; i < arr.length; i++) {
  middleIndex = Math.floor((newArr.length) / 2);
  if (target > newArr[middleIndex]) {
   newArr = newArr.slice(middleIndex);
   index += middleIndex;
  } else if (target < newArr[middleIndex]) {
   newArr = newArr.slice(0, middleIndex);
  } else {
   index += middleIndex;
   return index;
  }
 }
};
console.log(binarySearch(testArray, 3)); // should be 2

1. Declare index is equal to be 0, as well as middleIndex.
2. Declare newArr as arr.
3. Set middleIndex. It should be (newArr.length) / 2, and return the largest integer less than or equal to a given number with Math.floor() method.
4. If target is greater than newArr[middleIndex] (which means target is in the second half of the array), the second half of the array should be selected with slice() method. And it returns as newArr.
5. index is counted as index + middleIndex.
6. If target is less than newArr[middleIndex] (which means target is in the first half of the array), the first half of the array should be selected with slice() method. And it returns as newArr.
7. Otherwise, index is counted as index + middleIndex, and return index.
8. Iterate 3. to 7. until i become to be equal to arr.length — 1. (Which means it would be conditioned i < arr.length)

1st loop
i = 0
middleIndex = Math.floor(17 / 2) = 8
target > newArr[middleIndex] // ? 3 > 8 // False
target < newArr[middleIndex] // ? 3 < 8 // True
2nd loop
i = 1
middleIndex = Math.floor(8 / 2) = 4
target > newArr[middleIndex] // ? 3 > 4 // False
target < newArr[middleIndex] // ? 3 < 4 // True
3rd loop
i = 2
middleIndex = Math.floor(4 / 2) = 2
target > newArr[middleIndex] // ? 3 > 2 // True
index = 2