This playlist will be remembered in the history of Programming that there is someone who explains in such a way that the thing goes and fits in the middle brain and never moves to low or high part of the brain . It just remain there.
why the equality check with mid in the "else if "block and the "else" block of the base conditions if the equality check with mid is already false in the if condition?
WTF MAN. THIS CHANNEL IS JUST GOD LEVEL IN TERMS OF EXPLANATIONS. Man I am going to donate to your channel. The best freaking channel for coding explanations on youtube.
hi bro thanks for your effort i have 1 question, i tried both approach for linear complexity solution (iterative) i got 100% faster but for logN i got 75.51% faster in leetcode. why so? logN solution should be faster right?
@takeUforward I don't know how so many people have understood and submitted it. But the code is not giving the correct output for the input array A:[2,20,10,8] and target integer B=8. It is giving -1 but we all know answer should be 3. please help me anyone
@@sourabhchoudhary7289 can you help me with doubt ? : is this a valid we to solve this ques : We can also find the minimum element in the array and perform binary search on it's left and right and get the answer right ?
can you help me with doubt ? : is this a valid we to solve this ques : We can also find the minimum element in the array and perform binary search on it's left and right and get the answer right ?
Let's take the case: A[5,6,1,2,3,4] , target =6 According to your algorithm if A[low]this condition fails,so we'll slice the left half and make low=mid+1 , now what about 6 in the left half?
we are not completely ignoring left half because you see in the else block we are checking whether target lies in range or not. If it lies then only we are going with right half otherwise still going to left half
@take U forward here after the last else condition Do not miss to update Mid element mid = start + (end- start)/2 otherwise its gives only -1 for each testcase
The explanation is so awesome. I was just getting confused in between every time while coding this question. But then, I watched only 1/3rd of your video, and YAY! I got the whole approach and got the correct submission as well. Keep making content like this Sir!
Hi. I have a doubt. This is my solution - class Solution: def search(self, arr: List[int], target: int) -> int: lo = 0 hi = len(arr) - 1 while (lo = arr[lo]: #target lies in left half #adjust hi to be one less than mid hi = mid - 1 if target > arr[mid] and target = arr[lo]:` to `if target < arr[mid]` and change `if target > arr[mid] and target arr[mid]` Then the solution runs perfectly. What's going on here?
This approach didn't output the correct result for some reason. It kept giving -1. Finding pivot might be a better and safest choice, but just wanted to search for other approaches like this one, but somehow it failed.
bro listen for finding pivot is easy you just have to iterate through array and find the first element when which is less that 0th element but that will just increase its time complexity to nlogn isse badhiya linear search kr lete , aur lagega toh yaha binary search hi
what if the mid falls at index 5 and we neglect left half because its not sorted (which contained our target =0) wouldnt that give a -1 answer Which is wrong?
@@nikhilahuja9680 if left half is not sorted, then we are going to right half (which then would be sorted), But if element is not present in right half we are going on else, which means eventually we went to left half :)
when checking if *arr[mid] == target* , further check if these condition holds *if mid > 0 and arr[mid-1] == target* . if it holds, go left by setting *lo = mid +1* . **mid>0** ensures we have not gotten to the end of the array, which helps to avoid *index error* . *arr[mid-1] == target* check if element before the middle is not equal to target.
Hello striver bhaiya, i am not able to the solve it's adavance question on leetcode , problem is that if same question but all the elements are not distinct.. means elements may be repeating... Like arr = (1,0,1,1,1)
Yes, I checked that, this solution doesn't work for the reversely sorted arrays. Finding the pivot and applying binary search on the both side of the pivot saved me
can you help me with doubt ? : is this a valid we to solve this ques : We can also find the minimum element in the array and perform binary search on it's left and right and get the answer right ?
@@freshcontent3729 Yes it is possible. I found the largest element and then performed BS. Below is my Javascript implementation of the same: var search = function(nums, target) { const n = nums.length; let low = 0, high = n-1; let brkpoint = -1; while (low nums[mid-1]) && (mid == n-1 || nums[mid] > nums[mid+1])) { brkpoint = mid; break; } else if (nums[mid] > nums[n-1]) low = mid + 1; else high = mid - 1; } low = 0, high = n-1; while (low
![Lecture14: Binary Search Interview Questions [Google, Amazon, Microsoft] || ProblemSet - 2](/img/n.gif)
Please watch our new video on the same topic: th-cam.com/video/5qGrJbHhqFs/w-d-xo.html
This playlist will be remembered in the history of Programming that there is someone who explains in such a way that the thing goes and fits in the middle brain and never moves to low or high part of the brain . It just remain there.
Just want to say Thanksss Man!!!!
I have watched multiple videos but this one has the clear explanation than all the others. thank you!!
why the equality check with mid in the "else if "block and the "else" block of the base conditions if the equality check with mid is already false in the if condition?
understood
damm mann.. no one can take place of striver ..... understood +++++
respect++
WTF MAN. THIS CHANNEL IS JUST GOD LEVEL IN TERMS OF EXPLANATIONS. Man I am going to donate to your channel. The best freaking channel for coding explanations on youtube.
Do write "understood" if you understood, motivates me :)
Insta: instagram.com/striver_79/
Telegram: bit.ly/tuftelegram
Understood
hi bro thanks for your effort
i have 1 question, i tried both approach for linear complexity solution (iterative) i got 100% faster but for logN i got 75.51% faster in leetcode. why so? logN solution should be faster right?
@@rahulpatil4749 leetcode’s runtime feature is a flaw, ignore that, and focus on tc only.
@@takeUforward okay bro.
understood
i did two method
method 1 : p pass ,find pivot and then do binary search
method 2: strivers method
This is the most lucid and intuitive explanation for this question. I managed to solve this problem watch this video only once...
int search(vector& nums, int target) {
int low=0,high=nums.size()-1;
while(low>1;
if(nums[mid]==target) return mid;
if(nums[low]=nums[low] && target=nums[mid] && target
Great. I watched upto 4 videos struggling to understand. At last I found your video explained thoroughly. I'm super satisfied.
Searched it on many places, but finally understood it here… thanks a lot!!
I submitted this solution to leetcode
surprisingly linear search runtime was 3ms and binary search runtime was 11ms
I also got similar runtimes
Striver has told not to believe on Leetcode runtime %ages as it depends on other factors as well
[3, 1] target = 1
Test case not passes.
if the left portion is not sorted ,is we have to sort the left pportion?
in any other que.
thanx a lot buddy...ur vdos are really helpful :)
on youtube everybody taking the pivot element and then doing binary search
but strive bhaiya ,I am here we can do it with different methods as well
in first inequality check why are we checking a[low]
can anyone help me to find pivot element in rotated sorted array with duplicates?
why does it matter which side is sorted ?, in that example both left and right side is sorted
@takeUforward I don't know how so many people have understood and submitted it. But the code is not giving the correct output for the input array A:[2,20,10,8] and target integer B=8. It is giving -1 but we all know answer should be 3. please help me anyone
I have done code by myself but after saw your code it exactly looks Same =D !!
same goes for me :0
@@sourabhchoudhary7289 can you help me with doubt ? : is this a valid we to solve this ques : We can also find the minimum element in the array and perform binary search on it's left and right and get the answer right ?
can you help me with doubt ? : is this a valid we to solve this ques : We can also find the minimum element in the array and perform binary search on it's left and right and get the answer right ?
@@freshcontent3729 ofcourse we can but to final min element O(n) then for search O(logn) which is less efficient then discussed solution
@@sourabhchoudhary7289 We can actually find the min element in O(log n) time.
If we have duplicates like
7 4
3 3 3 3 4 3 3
Neither left nor right side is sorted
Actually the solution doesn't work for the reversely sorted arrays
Let's take the case:
A[5,6,1,2,3,4] , target =6
According to your algorithm if A[low]this condition fails,so we'll slice the left half and make low=mid+1 , now what about 6 in the left half?
int binarysearch(vector &arr, int n, int x)
{
int low = 0;
int high = n - 1;
while(low
we are not completely ignoring left half because you see in the else block we are checking whether target lies in range or not. If it lies then only we are going with right half otherwise still going to left half
@take U forward
here after the last else condition
Do not miss to update Mid element mid = start + (end- start)/2
otherwise its gives only -1 for each testcase
mid nikalne k liye jo right shift operator ki trick use kri hai , vo bhot osm lgi
Thanks for explaining so well
Is O(n log n) better than O(n)?
No , O(n) is better
The explanation is so awesome. I was just getting confused in between every time while coding this question. But then, I watched only 1/3rd of your video, and YAY! I got the whole approach and got the correct submission as well. Keep making content like this Sir!
Hi Striver, just one clarification, why "equals to" has been used?
That is instead of why we use =?
so that we can include extreme ends
yes when i remove equal to condition from line -10 ,its gives TLE, idk why
@@dreamer6911 are you talking about line no: 10 ?
@@anshumaan1024 Yea same i do that first then after seeing your comment i add that = then it accepted.
Finding pivot first and do binary search pivot as mid is the better way.
if(nums.size() == 1) return (nums[0] == target) - 1;
int low = 0;
int high = nums.size() - 1;
int mid;
while(low
10 march 2022 9:43am
Test Case# 1 : arr=[3,1] target = 1 expected op: 1 but your code is failed if it is in fully rotated
It runs perfectly fine; you must have made some mistake which I think you put ">" rather than ">=" in the first if condition.
understood
Video tho chalu hone de😂😂
Questions ka frequency badh gaya thanks bahiya
thank u for well wishes but i have headache
luv u
1:46
Why is there not a billion likes button on this video ?
how easily you just explained ... fab!!
thanks a lot bruh i was skipping this question in frustration of not understanding bt finally i got the logic.
Understood sir
I just discovered this channel, God bless you man. I really appreciate
understood ♥️
Amazing... It's amazing!✨💯🤩
You are my favourite teacher from now on... Striver!🥳
//understood :)
int search(vector& nums, int target) {
int low=0;
int high=nums.size()-1;
while(low>1;
if(nums[mid]==target)
return mid;
//check whether left half is sorted
if(nums[low]
understood bhaiya
Best explanation!!!
great explanation,ever seen
❤
can you please create series that includes all the problems , can be solved using binary search
Never thought this way, thanks!
Thanks striver, great explanation, after explanation I could solve by myself :)
OP explanation
Hi. I have a doubt. This is my solution -
class Solution:
def search(self, arr: List[int], target: int) -> int:
lo = 0
hi = len(arr) - 1
while (lo = arr[lo]:
#target lies in left half
#adjust hi to be one less than mid
hi = mid - 1
if target > arr[mid] and target = arr[lo]:` to `if target < arr[mid]` and change `if target > arr[mid] and target arr[mid]`
Then the solution runs perfectly. What's going on here?
bro you have not checked a condition whether the left side is sorted or not
the condition if arr[low]
❤❤
Understood 💯💯💯
Understoodddd ❤️❤️❤️
Thanks bhaiya
Thanks Bhai
Understood
Hey can u tell me from where I can learn binary tree and dp
Leetcode for Tree and for DP, I prefer gfg
try kashish mehndiratta channel for trees
Crisp and Clear Explanation! 👌👨💻
Thank you so much, Striver!!!!!!!!!!!!!
can anyone explain me this line => int mid = (low + high) >> 1;
1. ( x >> 1 ) == ( x / 2 )
right shift by 1 bit equivalent to division by 2
2. ( x
it same as int mid= (low+high)/2
What if elements are not distinct?
This approach didn't output the correct result for some reason. It kept giving -1. Finding pivot might be a better and safest choice, but just wanted to search for other approaches like this one, but somehow it failed.
bro listen for finding pivot is easy you just have to iterate through array and find the first element when which is less that 0th element but that will just increase its time complexity to nlogn isse badhiya linear search kr lete , aur lagega toh yaha binary search hi
yes it gives -1
you are the best explainer
Bhai pls upload one question daily my test is coming 😀
this c++ code is giving tle in leetcode...
brother use equal to condition also in else if, and else statement. Idk why its not working without it
Understood. Amazing explanation as always..
Bahut hi mast padhato ho bhaiya
precise and clean presentation
what if the mid falls at index 5 and we neglect left half because its not sorted (which contained our target =0) wouldnt that give a -1 answer
Which is wrong?
+1
@@nikhilahuja9680 if left half is not sorted, then we are going to right half (which then would be sorted), But if element is not present in right half we are going on else, which means eventually we went to left half :)
Understood !
But how to handle duplicate elements for the same question please tell
when checking if *arr[mid] == target* , further check if these condition holds *if mid > 0 and arr[mid-1] == target* . if it holds, go left by setting *lo = mid +1* . **mid>0** ensures we have not gotten to the end of the array, which helps to avoid *index error* . *arr[mid-1] == target* check if element before the middle is not equal to target.
Clear explanation 🙌
is this two pointer solution is O(logn)???
class Solution:
def search(self, nums: List[int], target: int) -> int:
low=0
high=len(nums)-1
while low
please reply @striver
this is O(n)
Thanks
@@nikitajaiswal9112 :)
You are brilliant teacher !!!!! ❤
Really nice video, I was able to code by myself
Hello striver bhaiya, i am not able to the solve it's adavance question on leetcode , problem is that if same question but all the elements are not distinct.. means elements may be repeating... Like arr = (1,0,1,1,1)
Finally understood it!
#DSAGangster
Understood for life.......Bhaiya!!!!!
Thank you for the solution, very helpful😃😄
can't we just fi d the peak element and then perform BS on two subarrays.
Watch the new one
Incomplete Explanation! What if a[low]>=a[mid] is not explained!
That's what the else condition is for🙃.
Great Explanation
I don't think this solution will pass all the test cases, better solution will be to find the pivot element in the array and then apply binary search
Yes, I checked that, this solution doesn't work for the reversely sorted arrays. Finding the pivot and applying binary search on the both side of the pivot saved me
However, finding pivot takes an extra (logn).
Greatttt!!!! Nicely explained:)))
Amazing explanation! Keep up the good work man.
can you help me with doubt ? : is this a valid we to solve this ques : We can also find the minimum element in the array and perform binary search on it's left and right and get the answer right ?
@@freshcontent3729 Yes. Its a valid solution
@@freshcontent3729 finding the minimum element has a worst case time complexity of O(n), but we have to solve it in O(log n).
@@prasannaprabhakar1323 can be found using binary search
@@freshcontent3729 Yes it is possible. I found the largest element and then performed BS. Below is my Javascript implementation of the same:
var search = function(nums, target) {
const n = nums.length;
let low = 0, high = n-1;
let brkpoint = -1;
while (low nums[mid-1]) &&
(mid == n-1 || nums[mid] > nums[mid+1]))
{
brkpoint = mid;
break;
}
else if (nums[mid] > nums[n-1])
low = mid + 1;
else
high = mid - 1;
}
low = 0, high = n-1;
while (low
Bhaiya on fire 🔥
Understood
Waah waahgreat
This code is not working for array
1 0 1 1 1
Target = 0 😭 in leetcode
what if my target is on left half while left half is not sorted.
🔥🔥🔥
understood.. Thank you
understood!
understood sir