Binary search - finding first or last occurrence of a number

See complete series on binary search here
Tutorial level - Intermediate.
Prerequisite: Knowledge of basic programming concepts like arrays, loops etc.

[lubokanev]

Putting captions on your videos is a great great idea. Especially for non native English speakers. I hope more people follow your example!

[sannidhiteredesai]

One more approach (considering that we have to find first occurrence) without using the result variable could be, just using the following conditions :
if( A[mid]<key ){
low = mid + 1;
}
else{
high = mid;
}
recursiveCall()

The mid element could be the first occurrence, so using this technique mid will also be a part of the next search

[hunghoangviet]

this is the first time I watch your video, It's very great. Thank for your sharing

[GoodDeedVideos]

Hi,

In this video, at time 8:44, when x is 10, low is 4 and high is 6, mid is 5 and a[mid] is 18, condition, x<a[mid] is satisfied, so acc to it, high = mid -1, which should be 4, and then low = 4, high = 4, mid = 4, but in video, high is done as 5, so please correct this mistake, and yes wonderful video, keep teaching

[robertsedgewick]

Best explanation on youtube for this problem. Thanks for the work!

[jennazhang]

Love your idea of setting result to -1. Neat and clear, thank you :)

[crimx]

Thanks! There is a simplified version all over the Internet which did not make sense to me. Now I get it!

[wakalaboom]

Great explanation! Would think that setting high = mid instead of mid-1, and low = min instead of mid+1, in case the next index is the only other occurrence

[shivaprashanthadha]

Hey instead of everything perform linear search from 0 index n then repeat it from n index in this way we can get both first n last occurrence.

[dicidicee]

How do you choose the problems you solve ? Are they actually asked by the top recruiters ? I found this one quite easy and classical. In any case, thank you for your well-explained videos !

[vijayendrasdm]

Hi
These videos are very very helpful. waiting for more videos

[md.nahidulalamchowdhury]

Thanks a lot. At 8:44, the High will be 4 but you wrote 5.

[anshusharma]

At 8:47, when high becomes mid-1, it should have high = 5-1 = 4

[debasishdalei]

Little bit wrong calculation at 8:48 time..i.e. in finding high.
Nice video mister

[ragha]

If all elements of array are the same, 10, wouldn't it take O(n/2) ~ O(n) time; so shouldn't that be the worst case?

[GOWRISANKARAS]

beautiful video! lucid explanation. thanks a million.

[namhuynh]

what if mid equals to decimal e.g. 3.5
Shouldn't mid = Math.floor((low+high)/2) ?

[tianma]

hi, good video, which software you make this video? thks

[parthgadoya]

I have Doubt in your explanation
At time 8:45 minute, please look at that..
In 3rd row and 2nd column [high],
Why high is not updated to 4 [mid - 1, as mid was 5]
high should be mid-1=4 but you have written it as 5..why??
Waiting for your response....

[nguyentranconghuy]

very nice, thank you so much, wish you come back soon, its been 1 year