Binary search - finding first or last occurrence of a number

[@lubokanev7436]

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

[@haldous2]

I just wanted to say thanks for all of your videos. I've been getting ready for an interview, re-studying cs concepts - your videos are the most clear and concise I've found. You get right to the point and makes things easy to understand. Kudos!

[@ArpanPathak]

You're my inspiration. The way you make animations, give examples, the way you precisely explain things is phenomenal and also the soothing voice. I started creating problem solving videos after watching you since my first year of college.

[@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

[@DuyTran-to9lk]

Deepak Swaroop corrected! I also noticed here

[@milnueve89]

Right. I was about to comment this. Great video, by the way!

[@aliciamejia7313]

A big THANK YOU! Had looked everywhere as I am not familiar with binary search and needed to implement it in VBA. First explanation that is easy, simple, and of course it works.

[@hunghoangviet7983]

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

[@robertsedgewick1266]

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

[@LamNguyen-nm1id]

this video is very useful for me to turn into a finding first and last occurrence altogether, thank you

[@crimx5342]

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

[@miracledoh4020]

this video is awesome, I found other solution like the one on geeksforgeeks confusing, with the biase thing

[@sannidhiteredesai912]

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]

[@bestdeal3385]

you give the best explanation ❤️👍🏻

[@alex-gz7ud]

Amazing!!! You make it so easy to understand!

[@jennazhang4968]

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

[@anantraman2379]

I think there is a mistake at 8:45 min where high should be mid -1 = 4...but by mistake you have taken it as 5... ThankYou

[@md.nahidulalamchowdhury9568]

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

[@vijayendrasdm]

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

[@brendananderson9102]

This is going to take some time for me to understand. Will probably have to find some practice code using it or something. Had to play video at 0.75 speed just to keep up!

[@kasyapdharanikota8570]

Very good explanation 👏

[@krishanudutta2943]

It was a brilliant explanation sir thanks a lot..

[@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

[@anshusharma11]

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

[@debasishdalei5371]

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

[@GOWRISANKARAS]

beautiful video! lucid explanation. thanks a million.

[@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 !

[@mycodeschool]

Courtinot David - Yes, these questions are quite often asked by top recruiters. In fact this is a favorite Google interview question. Someone has mentioned this in a comment too.

[@dicidicee]

mycodeschool Ok, tahnk you for your answer.

[@jennazhang4968]

Some changes can be added to this question, making it slightly different, but the searching idea is the same. I saw one on leetcode, I think someone meets this in an interview. oj.leetcode.com/problems/find-minimum-in-rotated-sorted-array/

[@Rakesh-ms7tn]

What is the software you are using for teaching ? Microsoft one note ?

[@shivaprashanthadha3002]

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.

[@tanvisharma6879]

Very well explained! Thanks:))

[@glovean9939]

Thank you. Very clear logic.

[@denny2826]

A really nice video. Love it! Thank you!!

[@abhishes]

Pretty nice explanation!

[@nguyentranconghuy6965]

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

[@ahbarahad3203]

For your kind information, he passed away in a car accident in 2016.

[@nileshgopale8528]

For your kind information , he is still alive and working in Google . MyCodeSchool was started by Animesh and later supported by Harsha ( Lord Harsha, One of the brilliant minded person in India ) .The person who Passed away in an accident was Harsha. So all these videos are created by Animesh . If you want to hear voice of Lord Harsha , then access Euclid's Algorithm from MyCodeSchool.

[@tianma201211]

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

[@AmanKumar-fd5ec]

Best explanation

[@parthgadoya5690]

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....

[@saumitrakaushal5369]

yes you are correct. but that does not make much difference to the above code , as while entering the loop next time (high+low)/2 = (4+4)/2 will give the mid as 4 only. I think it was just a miscalculation.

[@parthgadoya5690]

Okay.

[@ragha1988]

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?

[@manoharsegu4871]

Because BinarySearch pre-requisite is the input array need to be in sorted order. it will never be O(n) it will be O(Log n)

[@samanvaylakhotia5116]

No @ragha1988, In that case too, you're still performing binary search (& updating result). Had you been doing linear search even after finding the element in the array for the 1st time, then you would have O(n) in the worst case as you're pointing out. However, that's not the case here. We continue ahead with binary search, hence the worst case is also O(logN)

[@swatishama]

Good luck for the next time :)

[@rajeshgosain8862]

Do u have videos on java ?

[@thehhwy]

This algorithm seems to fail for the following case [20,21,22,23,23,23,24,25,1,2,3,4,5]. Can you please double check? I am trying to find the first occurrence of 5 but it gives -1. package search.binary; import java.util.Arrays; import java.util.LinkedList; public class FirstOccurrence { public static void main(String[] args) { LinkedList input = new LinkedList(Arrays.asList(20,21,22,23,23,23,24,25,1,2,3,4,5)); System.out.println(firstOccurrence(input,5)); } private static int firstOccurrence(LinkedList input, int x) { int low = 0, high = input.size()-1,mid; int result = -1; while(low

[@believec_me]

+Qihan Zhang ,Man above array is not sorted.Binary search only work for sorted array.Try it for sorted array.!

[@camilovalderrama9941]

try with [1,2,3,4,5, 20,21,22,23,23,23,24,25]

[@VlasiosSokorelosTheDarkwavist]

Thank you a lot for the video !

[@ravikiranbhovi1668]

Hi, what if an element is not present in the array? Wouldn't (return result) return the last calculated mid value incorrectly?

[@batam111]

Why is the time complexity of this is the same?

[@rishabhbhargava766]

Amazing Video!! Subscribed.

[@raghavchadha9133]

it gives result=-1 when i find element other than 10 ,,for eg when i fing 50 it give -1!!!!! why??? import java.util.Scanner; public class firstoccurenceofnumber { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int arr[]={2,10,10,10,50,30,20}; System.out.println("enter element to be searched"); int x=sc.nextInt(); int pos = binarysearch(arr, x); System.out.println(pos); } public static int binarysearch(int arr[],int x) { int low=0; int high=7; int mid; int result=-1; while(low

[@UtkarshGandhi96]

nice explanation. thanks

[@avrelyy]

greate explanation!

[@namhuynh6534]

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

[@JuanCarlosGarfiasTovar]

Great video!

[@someshkumargupta4304]

how mid = 1 in case of result = 3

[@vulturebeast]

(0+2)/2 = 1

[@nehaagrawal30]

You are genius

[@mamruthreddy6508]

Great Videos!!!

[@justinwong4149]

4:31 finding first occurrence

[@viswasthakur9455]

how to find third last occurrence of int of array

[@mrsloth-qw8pt]

Would this work on an un-sorted array?

[@nguyenhung2441]

Of course not

[@mahmoudabdelfatah1602]

in 8:46 high=4 not 5 ?

[@bishalrajbhattarai5482]

Lucky

[@shashankshekharismd]

Had I seen this video earlier, I would have solved the problem I couldnt in the Google Interview :(

[@mohammedfawaz289]

Did you get your job in Google?

[@evgenikunchev7741]

What about this? if(x == A[mid]) { while(A[mid-1] == x) { mid-- ; } return mid; }

[@volsurf1274]

this is precisely the linear search we are trying to avoid. Worst case for this is O(N) when the array has all duplicates.

[@abhaynanda1117]

great video

[@bolin6845]

Thank you very much !!!!!

[@satyanarayanareddytadi5585]

please can you check for this input 6 1 1 1 1 1 1 1 0 but according to this logic it was getting 2

[@rishbhardwaj1431]

Brilliant!

[@arvindgupta-zm7lz]

private static int binarySearchLast(int[] arr, int i, int len, int search) { // TODO Auto-generated method stub int result=-1; while(isearch) len=mid-1; else i=mid+1; } return result; } this is having some problem can you please help me

[@nichenishant]

Amazing!

[@SRIHARSHAKIRAN]

Hi. Thanks for excellent videos. I'm stuck on implementation of the same using recursion. Do you have that code by any chance? My code: private int binarySearchRight(List list, int element, int start, int end) { int ans = -1; if (start > end) { return ans; } else { int mid = start + (end - start) / 2; int val = list.get(mid); if (val == element) { ans = Math.max(binarySearchRight(list, element, mid + 1, end), mid); } else if (val < element) { return binarySearchRight(list, element, mid + 1, end); } else { return binarySearchRight(list, element, start, mid - 1); } return ans; } } Thanks Sri Harsha

[@sadmansakib007]

Awesome!

[@ahmidahmid9303]

a better implementation will be using linear searching to find the lowest and highest twins

[@ariabanazadeh1016]

It depends on a lot of things. If there is an array with a lot of duplicates binary search is better . but in an array with close duplicates linear is a lot better.

[@harshareddy3895]

Gud Video....:-)

[@mathstarz1168]

my code I wrote that allows for false to return left most integer and true to return right most integer. #include bool count = false; int binarySearchSpecial(const int array[], int size, int x, bool flag) { int mid; int start = 0; int end = size - 1; while(start x) end = mid - 1; else start = mid + 1; } return -1; } int main() { int found; int array[10] = {1,3,5,5,5,5,7,7,9,9}; bool decision = false; //swicth false for left most integer and true for right most right integer found = binarySearchSpecial(array, 10, 5, decision); if(found != -1 && count == false) std:: cout

[@srivatsakulkarni2580]

return 3; Game Over!

[@aswin2pranav]

Thanks :)

[@saginamvenkatcharan2111]

nuv thop bayya

[@arthur6892]

genius.

[@timhuang2214]

Programming

[@surebhands5810]

I changed as Before if(num == a[mid]) { return mid; } To After if(num == a[mid]) { if(mid + 1 < a.length && a[mid+1] == num) { return binhelper1(a, num, mid + 1, end); } else return mid; }

[@adarshverma3372]

Implementation for finding firstAndLastOccurene using the same method (This approach will work irrespecitve of array is sorted or not) public class FirstAndLastOccurrence { public static void main(String[] args) { int []inputs = new int[]{2, 6, 36, 36, 36, 47, 63, 81, 97}; OccurrenceDTO occurrenceDTO = new OccurrenceDTO(); int numberToSearch = Integer.MIN_VALUE; while (numberToSearch != -1) { System.out.println("Enter number to search"); Scanner scObj = new Scanner(System.in); numberToSearch = scObj.nextInt(); firstAndLastOccurrence(inputs, numberToSearch, occurrenceDTO, 0, inputs.length - 1); if (occurrenceDTO.getLastOccurrence() == Integer.MIN_VALUE || occurrenceDTO.getFirstOccurrence() == Integer.MAX_VALUE) { System.out.println("Number: " + numberToSearch + " is not present in the inputs"); } else { System.out.println("Number: " + numberToSearch + " exist in the inputs with first occurrence at: " + occurrenceDTO.getFirstOccurrence() + " and last occurrence at: " + occurrenceDTO.getLastOccurrence()); System.out.println("Number: " + numberToSearch + " appears: " + (occurrenceDTO.getLastOccurrence() - occurrenceDTO.getFirstOccurrence() + 1) + " times in the input" ); occurrenceDTO.setFirstOccurrence(Integer.MAX_VALUE); occurrenceDTO.setLastOccurrence(Integer.MIN_VALUE); } } } private static void firstAndLastOccurrence(int []inputs, int numberToSearch, OccurrenceDTO occurrenceDTO, int startIndex, int endIndex) { if (startIndex > endIndex) return; int mid = (startIndex + endIndex) / 2; if (inputs[mid] == numberToSearch) { if (occurrenceDTO.getFirstOccurrence() > mid) occurrenceDTO.setFirstOccurrence(mid); if (occurrenceDTO.getLastOccurrence() < mid) occurrenceDTO.setLastOccurrence(mid); } firstAndLastOccurrence(inputs, numberToSearch, occurrenceDTO, startIndex, mid - 1); firstAndLastOccurrence(inputs, numberToSearch, occurrenceDTO, mid + 1, endIndex); } } Although this method execution will take some time around t(n) = n + log n * c taking the higher-order term so t(n) would be near to O(n).

[@ContentWalaHitesh]

Great video

[@sahithiodnam8255]

thank you:)