Binary Search
Published in
2 min readSep 30, 2020
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
- Declare
index
is equal to be0
, as well asmiddleIndex
. - Declare
newArr
asarr
. - Set
middleIndex
. It should be(newArr.length) / 2
, and return the largest integer less than or equal to a given number withMath.floor()
method. - If
target
is greater thannewArr[middleIndex]
(which meanstarget
is in the second half of the array), the second half of the array should be selected withslice()
method. And it returns asnewArr
. index
is counted asindex
+middleIndex
.- If
target
is less thannewArr[middleIndex]
(which meanstarget
is in the first half of the array), the first half of the array should be selected withslice()
method. And it returns asnewArr
. - Otherwise,
index
is counted asindex
+middleIndex
, and returnindex
. - Iterate 3. to 7. until
i
become to be equal toarr.length — 1
. (Which means it would be conditionedi < arr.length
)
1st loopi = 0
middleIndex = Math.floor(17 / 2) = 8
target > newArr[middleIndex] // ? 3 > 8 // False
target < newArr[middleIndex] // ? 3 < 8 // True2nd loopi = 1
middleIndex = Math.floor(8 / 2) = 4
target > newArr[middleIndex] // ? 3 > 4 // False
target < newArr[middleIndex] // ? 3 < 4 // True3rd loopi = 2
middleIndex = Math.floor(4 / 2) = 2
target > newArr[middleIndex] // ? 3 > 2 // True
index = 2