JavaScript Algorithms - 18 - Recursive Binary Search

📱 Follow Codevolution

Recursive Binary Search
JavaScript Algorithms
Algorithms with JavaScript

[Avatar-Roku]

The Binary search is definitely more difficult than the linear but I hope after practicing 3-4 times, I will get it all.

[whereIsJerome]

Another approach, with a slightly more terse syntax, might be something like this:

```
const binarySearch = (array, target, head = 0, tail = array.length - 1) => {
if (head > tail) return -1;
const middle = Math.floor((head + tail) / 2);
if (array[middle] === target) return middle;

return (array[middle] > target) ?
binarySearch(array, target, head, middle - 1) :
binarySearch(array, target, middle + 1, tail);
};
```

[lautipueyrredon]

function RecursiveBinarySearch(arr, target, leftIndex=0, rightIndex= arr.length-1 ){
let middleIndex = Math.floor((leftIndex + rightIndex)/2);
if(arr[middleIndex]===target) return middleIndex;
if(target < arr[middleIndex]) return RecursiveBinarySearch(arr, target, leftIndex, middleIndex -1 );
if(target > arr[middleIndex]) return RecursiveBinarySearch(arr, target, middleIndex + 1, rightIndex);
}

[sameerhussain]

const recBinarySearch = (arr, target)=>{
if(!arr)
return -1;

arr.sort((a, b) => a - b)

const search = (arr, target, leftIndex = 0, rightIndex = arr.length - 1)=>{
let middleIndex = Math.floor((leftIndex + rightIndex) / 2)

if(arr[middleIndex] === target)
return middleIndex

if(target < arr[middleIndex]){
return search(arr, target, undefined, middleIndex - 1)
}else{
return search(arr, target, middleIndex + 1)
}
}
return search(arr, target)
}

[Ashwini]

Hi Vikas, thanks for such a wonderful video.

[Sachinsingh-ilso]

let arr = [-5, 2, 4, 6, 10];
let target = 6;

const findIndex = (arr, t, left = 0, right = arr.length - 1) => {
if (left > right) {
return -1;
}

let mid = Math.floor((left + right) / 2);
if (arr[mid] === t) {
return mid;
}

if (arr[mid] < t) {
return findIndex(arr, t, mid + 1, right);
} else {
return findIndex(arr, t, left, right - 1);
}
};
console.log(findIndex(arr, target));

I used this approach is this right ?

[mitkomilev]

Binary search is so easy got it from the first time. It's like setting min and max for certain interval and you search for the target in that interval.

[ayoubash]

thank you for your effort i have question the binary search in general it cant give us a correct answer if we have array of 7 elements for example

[faithfulonoriobakpo]

I think you write another function because of extra parameters i.e leftIndex and rightIndex needed. What if we added them in the recursiveBinarySearch function and gave them default values.

See illustration below.

function recursiveBinarySearch(arr, target, leftIndex = 0, rightIndex = arr.length - 1){
if(leftIndex > rightIndex) return -1;

let middleIndex =

if(target === arr[middleIndex]) return middleIndex;

if(target < arr[middleIndex]){
return recursiveBinarySearch(arr, target, leftIndex, middleIndex-1);
}else{
return recursiveBinarySearch(arr, target, middleIndex+1, rightIndex);
}
}

Here we've written just one function, code is shorter and takes less memory.

Below is a one line implementation. Not shorter though.

const binarySearch = (arr, target, leftIndex = 0, rightIndex = arr.length - 1) => leftIndex > rightIndex? -1 : target === : target < binarySearch(arr, target, leftIndex, Math.floor((leftIndex+rightIndex)/2) - 1) : binarySearch(arr, target, + 1, rightIndex);

[AkashGupta-pccb]

I did not even think of writing a separate function, was stuck on how could that be done recursively with a single function. Hard stuff is this

[srudsalam]

function search(arr, n, left = 0, right = arr.length - 1) {
const middle = Math.floor((left + right) / 2);

if (left > right) return -1;
if (arr[middle] === n) return middle;

return arr[middle] < n
? search(arr, n, middle + 1, right)
: search(arr, n, left, middle - 1);
}

const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 22];

console.log("10: ", search(arr, 10));
console.log("6: ", search(arr, 6));
console.log("2: ", search(arr, 2));
console.log("20: ", search(arr, 20));

[srustithakkar]

why do we need to use another function ?
Can't we do it like:
function recusiveBinary (arr, t){
let MiddlePoint = Math.floor(arr.length/2);
if (arr.length < 1){return -1}
if( MiddlePoint = t){
return arr.indexOf(MiddlePoint)
}
let leftArray = arr.slice(0, MiddlePoint);

let rightArray = arr.slice(-MiddlePoint);

if( t > arr[MiddlePoint]) {
recusiveBinary(rightArray, t)
}else{
recusiveBinary(leftArray, t)
}
return -1
}

comments appreciated!

[thetech]

At 5:00, why couldn't you just do if(arr.length === 0) return -1
instead of
if(leftIndex > rightIndex) return -1?

[luckylam]

Thank you for the video.

One question, why you didn't use `const` middleIndex instead of `let`? It's obviously not reassigned. Thanks

[nayabrasool]

instead of / 2), we can use Math.floor(arr.length/2)

[venkataramanasubramanyambh]

How about this??

function binarySearchRecursive(sortedArray, searchValue) {
if (!sortedArray.length) return -1;
const middleIndex = - 1) / 2);

if (sortedArray[middleIndex] === searchValue) {
return middleIndex;
}

if (searchValue < sortedArray[middleIndex]) {
return binarySearchRecursive(
sortedArray.slice(0, middleIndex),
searchValue
);
}

return (
middleIndex +
1 +
binarySearchRecursive(
sortedArray.slice(middleIndex + 1, sortedArray.length),
searchValue
)
);
}