2.6.2 Binary Search Recursive Method

Hello Sir, lots of respect to your teaching. I have implemented this in JS : please check :)
Thank You.


let arr = [3,6,8, 12,14,17, 25, 29, 31, 36, 42, 47, 53, 55, 62];

function recursive_binary_search(target, low, high) {
const mid = Math.round((low + high)/2);
if (arr[mid-1] === target) {
console.log(`Element Found In Position : ${mid-1}`);
} else {
if (low >= high || (mid >= arr.length)) {
console.error("Range Error: Element Not found!");
} else {
if (arr[mid-1] < target) {
return recursive_binary_search(target,(mid-1)+1, arr.length )
} else if (arr[mid-1] > target) {
return recursive_binary_search(target,1, mid-1)
}
}
}
}

recursive_binary_search(2, 1, arr.length)

I love u sir you're my bahubali

why isn't the order of binary search is O(log n to the base 2)

wowww

Sir, a function can return the function itself which you have done int binary search algorithm ???

I'm a non-cs background student and even i can understand such simple explanation. Hats off to you sir for your contribution sir.

Great to come across your clips on algorithm, you lecture just rolled away huge pressure off my neck. Thanks Sir

i wish there was a coding part also. i Have NEVER seen a teacher with this level of understanding in data structures.

Thank you soo much sir

I know that my ex will always come here because she is studying algo now. I just wanna say, I miss you and I love you to the moon and back. I really do. Keep it up with your studies ok? ❤

There is a slight mistake in your algorithm if(l==h) will throw you a stackoverflow error instead you should use if(h<=l).........

Master what kinds of problems we can divide? like in case of the binary search above?

I have just one thing to say: Thank you!

That's the thought I was looking for, thanks

Why are we using return in if else block..instead we can avoid return in if else block
I think return mid is sufficient

One thing i observed is that if we take an even sized array, we are getting tree of depth 5 instead of log(16)= 4. Please let me know if my observation is valid

👍👍👍

Bari Sir, hats off to you. I brag to my friends that I was your student and thought me DSA during my engineering and every time I have an interview I make sure I go through some of your videos..

cannot express my gratitude. Thank you Mr Abdul - all of your videos are priceless! you're a legend. Thank you for helping to improve

Thank you Mr Abdul - all of your videos are priceless! you're a legend. Thank you for helping to improve

31st video

Thanks for this helpful playlist, you are the best.

I tried to implement the algorithm as it is in the video, it didn't work except for values already in the array.

My recommendation:
1- remove the if block
2- Modify the else block to be "if (l <= h)"
3- Add else block which returns -1 in case "l > h"

Here is my implementation in C++:

int BinSearch(int l, int h, int key,vector<int> arr) {
int mid;
if (l <= h) {
mid = (l + h) / 2;
if (key == arr[mid])
return mid;
else if (key < arr[mid])
return BinSearch(l, mid - 1, key, arr);
else
return BinSearch(mid + 1, h, key, arr);
}
else
return -1;
}

Finally, I want to thank you for your effort in this series which really helps me to learn from scratch.

Thank you for your hard work.

why aren't we using "while(h>=l)" in the else statement?

So helpful! Thank you Sir! Btw would you please enable the subtitles? My english is not very good. Thank you.

did he forget to input the array in the parameter?

Explain examples sir

Made this very easy to understand, divide and conquer!

you'd also have to check if your lower bound is greater than you upper bound, such as for the input [2,5], target = 0

Algo worked fine when item is inside the array or greater then the array elements but fails, when item is less then the entire array elements.

Pass:

1-> When item is present
2-> When item is greater then all the items present

Failed: When Item is less then all the items

int[] a = {2, 3, 4, 10, 40};
int searchItem = 1;
int low = 0;
int arraySize = a.length;
int high = arraySize - 1;

private static int search(int[] a, int low, int high, int searchItem) {
if (low == high) {
if (a[low] == searchItem)
return low;
else
return -1;
}
else {
int mid = (low + high) / 2;
if (searchItem == a[mid])
return mid;
if (searchItem < a[mid] )
return search(a, low, mid-1, searchItem);
else
return search(a, mid+1, high, searchItem);
}
}


Condition need to be added :

Instead of: if (low == high) {
we need to put one more check there:
if (low >= high) {

I can't see the method where you find the first occurrence of the element to look for and what if your array r<l, hic

Thank you for these videos Abdul Bari. I normally struggle to learn from videos, but your concisesness helps so much. I know that my focus won't be wasted, so I can listen intently for the full video.

This is, by far the best tutorial for learning binary search I've ever seen.
Many people have sufficient knowledge and skills and they try passing them to others
but a few of them can deliver them in a convenient method like Abdul Bari Does.

God bless you and your loved ones..... Keep rising... 🥰😘

Amazing!!!

Sir, how is BinarySearch Divide and Conquer? We are not dividing the problem into multiple sub-problems. We are, at every step, decreasing the problem into a single smaller problem. We don't divide the array into 2 halves at each stage and process both arrays. I read on internet it is a Decrease and Conquer problem. Is this true?

Sir i dont think l > h , case is covered which actually could occur

This is a truly great video, but wouldn't we want to include the sorted array as one of the parameters for the recursive binary search?

You are great❤️❤️

I can finally write the code after this lecture series! Thank you from South Korea.

ofc the microphone is clipping...

Thank you x 100

Sir in your recursive code, you didn't give a condition for when the element can't be found, i.e. you have to give a condition that when l>h return -1. Other than that amazing lectures

Sir you should be guiding students for companies like google and amazon. Also please write a book on Data Structures definitely I will buy.

🤯

Great explanation