Javascript Algorithm: Binary Search on sorted Array

Solution 1:

var arr = [23, 45, 67, 78, 89, 96];

function binarySearch(arr, ele) {

if (arr.length == 0) {

return false;

}

if (arr[arr.length - 1] < ele) {

return false;

}

if (arr[0] > ele) {

return false;

}

var middle = Math.floor(arr.length / 2);

if (arr[middle] == ele) {

return true;

}

if (arr[middle] < ele) {

var newArr1 = arr.slice(middle + 1);

return binarySearch(newArr1, ele);

} else {

var newArr2 = arr.slice(0, middle);

return binarySearch(newArr2, ele);

}

}

var res = binarySearch(arr, 67);

console.log(res);

Solution 2:

function binarySearch(sortedArr, key) {

var start = 0

var end = sortedArr.length - 1

while (start <= end) {

var middle = Math.floor((start + end) / 2)

if (sortedArr[middle] === key) {

return middle

} else if (sortedArr[middle] < key) {

start = middle + 1

} else if (sortedArr[middle] > key){

end = middle -1

}

}

return -1

}

var arr1 = [234, 43, 55, 63, 5, 6, 235, 547, 23];

var sortedArr = arr1.sort((a, b) => {

return a - b

})

console.log("sortedArray", sortedArr)

var result = binarySearch(sortedArr, 63)

console.log(result)

Overall, this implementation has a time complexity of O(log n),

which is much faster than a linear search with a time complexity of O(n).