2.6.2 Binary Search Recursive Method
Vložit
- čas přidán 10. 09. 2024
- Divide and Conquer
Binary search Recursive method
Analysis
PATREON : www.patreon.co...
Courses on Udemy
================
Java Programming
www.udemy.com/...
Data Structures using C and C++
www.udemy.com/...
C++ Programming
www.udemy.com/...
i wish there was a coding part also. i Have NEVER seen a teacher with this level of understanding in data structures.
Your mastery in converting complicated algorithmic steps into the simple stages is impressive.
Sir you are hero , superb !! Allah lambi zindagi de :)
Sir, u are my hero sir
👑God of algorithms 👑
😇🌞😎💻
"Simply in the nptel outdated teachers are teaching the same concept for hours together
And u are awesome sir without missing out any of the concepts u are teaching better than them sir"
As enstien said "if u can't explain in simple ,u have to understand well enough"
For the above qoute Ur best example sir
Thank u sir it's helping me a lot
God bless u sir
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..
31/83 videos in, bought your course on data structures. Maybe jumping ahead of myself, but you're amazing at explaining this.
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.
Being from non cs background, it was very difficult for me to find time complexity of a algorithm. Your recurrence relation series has helped me alot.
I'm a non-cs background student and even i can understand such simple explanation. Hats off to you sir for your contribution sir.
You're so unique, I failed algorithm because I didn't understand it when my lecturer taught me. I am sure I will scatter my Saturday's exam curtesy of you Dr Abdul Bari.
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"
Here is my implementation in C++:
int BinSearch(int l, int h, int key,vector arr) {
int mid;
if (l
There is a slight mistake in your algorithm if(l==h) will throw you a stackoverflow error instead you should use if(h
I never understood recursion, but after watching this video I know all of it
thanks, Abdul sir!
I can only shay Thank You. I Just passed my algorithm exam with honors.
Thank you, thank you and again thank you
now i am clear you teach it better then , even our university teacher.
From which university you are?
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.
Sir you should be guiding students for companies like google and amazon. Also please write a book on Data Structures definitely I will buy.
I know my DAA is in safe hands now.
and 2 years later, I do too
@@amuzak9063 lmao Samw😂
DAA or DSA??😅
@@bageshwardham-1Msame question
cannot express my gratitude. Thank you Mr Abdul - all of your videos are priceless! you're a legend. Thank you for helping to improve
I can finally write the code after this lecture series! Thank you from South Korea.
That's the thought I was looking for, thanks
this also is a good algorithm:
def RBinarySearch(arr, value,l = 0,h = 0):
if(l>h):
return -1
mid = int((l+h) /2)
if(arr[mid] == value):
return mid
elif (value > arr[mid]):
l = mid+1
else :
h = mid-1
return RBinarySearch(arr,value,l,h)
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29]
print(RBinarySearch(arr,25,0,len(arr)-1))
Thank you Mr Abdul - all of your videos are priceless! you're a legend. Thank you for helping to improve
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
The first condition where l==h is when the algo will return 0 when an element is not found, in case the element is not found, before l becoming greater than h , it first becomes equal to l.
Great to come across your clips on algorithm, you lecture just rolled away huge pressure off my neck. Thanks Sir
only one word sir """SUPERRB"""
God bless you and your loved ones..... Keep rising... 🥰😘
I have just one thing to say: Thank you!
Why are we using return in if else block..instead we can avoid return in if else block
I think return mid is sufficient
Sir
instead of that if l==h block
if we just check l>h and return wouldn't it still do the same considering we are already comparing with a[mid] later?
Thank you
One question: Aren't we suppose to return 0 for successful events and -1,1, etc for unsuccessful events?
Great lecture series btw.
Correct. The tutor here has array indices starting at 1. So function can return 0 if key not found.
Most languages have array indices starting at 0, so return -1 if not found.
Made this very easy to understand, divide and conquer!
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
I love your way of delivering... Awesome
I am facing a problem with this algorithm, if the key is not found then the function is not returning what's expected. The program just terminates. I think there needs a (l > h) terminate condition.
I noticed this too. This can easily be solved by another if chain in the first if.
if () {
...
}else if () {
...
} else {
return -1
}
Master what kinds of problems we can divide? like in case of the binary search above?
Binary Search has only Divide strategy and not conquer strategy. So, does it come under Divide & Conquer ?
super sir, your videos are really very helpful, you make the subject simple so that even a new student can understand, I am able to write programs watching your videos, thank you so much.
Great content . Quick correction : The recurrence relation is 2 * T(n/2) +1
I can't see the method where you find the first occurrence of the element to look for and what if your array r
passing arguments (l,h,key,Arr).. I think array missing in the passed arguments sir
Call a constructor.
In such cases array is always declared as global variable. You can also pass it as argument but that would take more system memory.
@@vineetwidhani8513 Pass the reference then?
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
Sir i dont think l > h , case is covered which actually could occur
Please sir ...i'm little bit confused... I need your help...please reply and tell me that binary search iterative method also use divide & conquer strategy or only recursive approach is using divide & conquer for binary search
Superb Sir ji thnq for giving algo video
If they ask binary search in question paper which method have to follow either iterative method or recursive method ???
Ok sir..thank you so much 😊
The array starting at index 1 is confusing me, but in general awesome video! Thanks a lot!
bro its good.my friend suggest u and i was lucky i got u
a=[3,6,8,12,14,17,25,29,31,36,42,47,53,55,62]
z=int(input("Enter the number you want to search: "))
low=0
high=len(a)-1
while low
Thankyou sir 🥰😄
shouldn't we have to pass array into the recursive function? or should array be a global variable. Am i wrong guys?
Yes we need to pass array to the fuction.
We can just capture the main logic behind so you will have no problem if it is kept in mind.
Sir, a function can return the function itself which you have done int binary search algorithm ???
Thank you soo much sir
Great explanation
Sir, I just bought your Data Structures course on Udemy. I have working experience in Java but the course is taught in C and C++, will it help me in detail with respect to Java or will i be missing something?
a gold mine in youtube
What if there are duplicate values? We want the first one.
Input:
array= [1, 5, 5, 5, 6]
value = 5
Expect: 1.
But your approach would divide the array in half and check the mid element, array[2]. array[2] is 5, and that matches the value you searching for, so your function would return 2. Instead, it should return 1.
mistake in algo-----> not checked condition for low>high if(low>high) return -1;
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 what's the meaning of return in coding why we do this and when?????
why isn't the order of binary search is O(log n to the base 2)
Best Ada teacher♥️♥️♥️♥️
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.
Thank you for your hard work.
sir do we want to define the l and high values in recursive algorithm
Sir time we get by iterarative algorithm and recursive algo is same log(n) so which one is best for use .
Batch of 2023 ❤ still masterpiece for Algorithm
Besttttttttttt teacher
If element not found you return zero but what will happen if index of the element is zero?
never though I'd have Prakash Raj teach me CS
Wouldn't the code still work if we only wrote what's in the main else block?
Thank you sir and great explanation
but this is not really D&C algorithm as it just reduces the problem but it does not generate separate results for sub-problems which are later merged on like in quicksort or parallel sum
sir please make videos on python also
Sir, where is the condition to check (l>h)??
how can be lower limit greater than the upper limit
@@adityac4418 it can come think of a subarray of 2 size and then mid is 0 index , now consider key smaller than mid
Btw why is it t(n/2) for the returning functions even if rbinsearch function takes t(n) time they are the same aren't they
it recursively called for only half of the array numbers...so n/2
@@pragmatic_p8 Thanks for your clear explanation! I was also confused about it, but now I totally understand.
I love u sir you're my bahubali
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) {
Sir, you're great !
Thank you🙏
where is combine step in binary search after divide and solve step?
+Abdul Bari without combing it full fill the divide and conquer guidelines? as it says there are 3 phases divide conquer and combine
Sir generly any problem written in iterative time complexity take more or equal to recursive ?
Abdul Bari sir iterative and recursive are equailvent power? If yes then y we are using recursive ?plz explain .greedy, dynamic approach following iterative or recursive or both
Not satisfied 😢
thanks for this video!
Sir, why did you put a condition to check whether l is less than h?
What if the element isn't present in the array. The call should be returned rather than calculating mid in else.
Thank you.. Sir....
You are great❤️❤️
mja aa gya sir
did he forget to input the array in the parameter?
Thank you x 100
i donno why he took that pause 0:02 , anyways he's best!
Sir will you please provide the source code
Don't we need to pass the Array as one of the parameters (which in this case is A)? It does not really matter but if you want to be pedantic then I think you should pass A as one of the parameters too.
Makes sense.I was just being pedantic. Thanks for these awesome videos!
Nice video sir,but i think it will not work for cases like key=1 and array=[2,3];
The base case should be:
if (low > high) {
return -1;
}
Since 1 is less value than 2, the first element of the array, the recursion in this lesson will run without reaching its base case. At some point, high will be less than low which would then result in an error. So it's best to define your base case as the above example.
Thank U Sir
Tqsm sir
Amazing!!!
Explain examples sir
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?