Implement Upper Bound & Lower Bound with Binary Search | CP Course | EP 41

In this video i discuss how you can implement upper_bound and lower_bound using binary search

Question To practice :
Upper Bound and Lower Bound questions are those of binary search only, So try solve all the easy and some easy medium in below lists. Please note that not all questions present in below links can be solved using upper_bound and lower_bound but most of the easy ones can be.

Timestamps:
Code & Explanation : (0:00)
bloopers : (11:09)

Be a part of our awesome Community. Join

You can follow me on below platforms for all the latest updates

Blog(Not frequently updated)

Hashtags
#upperbound #lowerbound #binarysearch #competitiveprogramming

[ANUJKUMAR-fubk]

Bhaiya in every video description put the link 🔗 of best question related to that topic. Aapka Technic of teaches unique hai, keep it up 👍.

[deepakbaxi]

Bhaiya, Mai internet me available various resources me try kr chukka hun even unacademy bhi but apke videos me kuch alag hi level ka intrest ata h

[manojgollapelli]

Everything is crystal clear.. Thank you luv sir

[anuj]

thank you, bhaiya my confusion got cleared

[PhoenixRisingFromAshes]

Jahapana Tusi great ho tofa kabul awesome video

[fahmidurarnob]

Thanks Bhai
This Course is helping me a lot🖤

[anuragtripathi]

Luv bhaiya bohot bohot thank you.
Ur aap kucch algorithms(techniques) bhi bata na joki maximum questions me kucche jate haiii..plzz if you can.

[SauravKumar-kjuu]

But, lower_bound is also used as finding point of insertion, so either 0 or n(size of vector) should be returned. Not -1 . That's what I interpreted.

[SandeepSingh-xpzi]

If you are asking for lower bound of 5 and upper bound of 5 in array 2, 3, 4, 6, 7 then is should be 6 and 4 respectively right?
How lower bound and upper bound can be 6 only.?

[nitishkushwaha]

Alternate codes for lower_bound and upper_bound functions :
// lower bound
int lower_bound(vector<int>&v, int val)
{
int l=0, h=v.size()-1;
int mid;
while(l<h)
{
mid=(l+h)/2;
if(v[mid]<val) l=mid+1;
else h=mid;
}

if(l<v.size()-1) return l;
else
{
if(val>v[l]) return -1;
else return l;
}


}

// upper bound
int upper_bound(vector<int> &v, int val)
{
int l=0, h=v.size()-1;
int mid;
while(l<h)
{
mid=(l+h)/2;
if(v[mid]<=val) l=mid+1;
else h=mid;
}

if(l<v.size()-1) return l;
else
{
if(val>=v[l]) return -1;
else return l;
}
}

[abc-ymzs]

sir generally after doing binary tree approach high<low that means a[high]<a[[low] then how you can check the a[low]>=find sir

[PARTHLADIWAL]

sir i have a doubt -
that what is the need to check the higher index as when finally just two elements are remaining and we are reducing our subspace just so that every element in it satisfies our condition so our ans should be always the lower index ? am i correct ?

[dpkkumar]

Bhaiya which platform are u using for coding, could u pls tell me ?
If anyone knows, pls bta do 🙂

[harshitchaubey]

Course to Acha he hi ... I want to appreciate editing and background music 🔥
Which software you use for video editing???

[worldwarheroes]

why did you write - int mid; two times ?

[Abhisumant]

Bhai ek baat bata do pls🙏
Aapne laptop me setting kaise kari ki program apne aap band ho jata hai 7 sec se jyada tym lene pe

[Draxper]

Awesome teaching!! Background music name?

[yashjain]

Basically in this video, you have implemented the inbuilt upper_bound and lower_bound functions, so your implemented code must return the same output
as the inbuilt functions do,
but Some output did-not match :

Use these inbuilt function : upper_bound(a.begin( ), a.end( ), 8) - a.begin( ); return 6, where as your code return -1, so seemingly they are not same, please correct me if i am wrong and vice-versa.

[BMEFaisal_khan]

Luv bhaiya binary search ki playlist me Or video upload karenge kya?

[silverzero]

(high+low)/2
ke badle
low + (high-low)/2
kar dete overflow avoid karne