Algorithms: Binary Search

[@BigJDawg6969]

That keyboard click is very satisfying

[@BrianFaure1]

It's like a rubber mat or something

[@im-a-trailblazer]

Someone now gets the idea of Binary Search..

[@Samdroid_]

try mechanical keyboards you will love it

[@iNet16]

macbook keyboard

[@nikhilnagrale]

@@iNet16 they are boring mechanical keyboards are best

[@yvesbff5107]

love having a test tomorrow​ on something you know nothing about

[@allroundlad]

I relate to this religiously

[@selenatorbirdie9305]

I have the test today in like an hour 😂

[@ll-sz9fl]

But more I love Ariana ♥️

[@abbGames2000]

Basically half an hour left for my exam and still need to learn this and bubblesort algorithms

[@gueloremanuel2639]

@@allroundlad ...

[@MichaelCarolin]

A key thing to know about binary search is that is not strictly limited to sorted arrays. It's just a method for efficiently narrowing a search range (in log(n) steps) in order to find a value that meets a criteria. You can use binary search to find the median in an unsorted array, for instance.

[@bcoz1492]

could you explain why it doesn't need to be sorted? are you referring to quickselect?

[@drakata27]

explain it lil bro

[@alexcomas2934]

This is such a simple implementation. Other places have an overcomplicated solution lol.

[@memo6032]

For anyone wondering why we need to add the first number to the last number, after all it doesn't make sense when our first element is 0 or 1, we do that becuase it's necessary when we go deeper through the array. If you are at the 6th element, for example, and the 9th element is your last element, adding them together is necessary to get the middle element.

[@charlesikemefuna6481]

Thanks for this Gayle. Great theoretical overview with an example to illustrate the point, followed by the hands on coding implementation. Truly great stuff.

[@TheMrkazsam]

Great video, made a confusing two hour lecture make sense in 6 and a half minutes.

[@ayushsingh9732]

I read her answers on quora for so long, but I didn't even know she was so famous

[@its_neel_ok]

whats her @

[@zackogoma2800]

my name is zach,my bro is andy.What a coincidence

[@cinquain0]

That’s the best description of binary search I’ve ever heard

[@traviswentz4248]

These videos are so nice. They're concise and clear in their explanations. Thanks for the videos Gayle Laakmann McDowell and HackerRank!

[@betocollin]

If you do this in Javascript, don't forget to Math.floor it: const mid = Math.floor(left + ((right - left) / 2));

[@robbeandredstone7344]

Why does everything have to bee floored in JS?

[@Azelphur]

​@@robbeandredstone7344 In Java, you are using Integers. Integers can only be whole numbers (so no decimal place). When you do Integer division, you always floor the result. So to use a real world example, lets say array.length is 8. Therefore left is 0, right is 7 (since array.length-1 = 7) In Java, you are running int mid = 0 + ((7 - 0) / 2);. This is 3.5, but that's not an integer. The result gets floored and becomes 3. mid gets set to 3, and on the next line you try and access array[3] - this works fine. In Javascript, you are using its "number" type, which is actually a float. So mid = 0 + ((7 - 0) / 2); sets mid to 3.5. Then on the next line you try and access array[3.5], and as you can imagine, things go wrong from there. It's always important to know how your programming language (and even version of that language) handles division, for example, Python 3.x returns a float for all division, while Python 2.x returns an integer.

[@robbeandredstone7344]

Thanks

[@jandrorojas6714]

@@robbeandredstone7344 and why do everybody have to throw some shade about JS?

[@bikeshbaral1685]

why we should use left+(right-left)/2 instead of (Left+right)/2 . or what does data overflow really mean.

[@Bayo106]

I have no clue why some people do the first one as the second one is easier to understand and shorter

[@rodrigocolasso]

bikesh baral If you sum two integer you could overflow the variable ( put more value than the variable can handle). With the second option this scenario would never happen.

[@patrickstival6179]

I think it starts well but when she dives into code it gets confuse. Feels like it needs more explanation or abstraction while she writes it down, such as a line-to-line description. Many people got confused about the overflow-prevention expression and the mid point manipulation.

[@nickgattuso]

You just need more experience programming then. I found this very easy to follow. Thats why this is a video series. You can easily pause the video and think, rewind etc.

[@namlehai2737]

Makes perfect sense but only because ive known this already. Yeah...

[@UnrecycleRubdish]

Exactly. She assumes way too much and skips many steps. Regardless of programming level, this is a poor way of teaching.

[@centurion8158]

This is such a wonderful explanation on this topic, i've been struggling with this for a while

[@shawnscientifica6689]

In practice I highly suggest to never tweak unless absolutely necessary. It's too easy to tweak yourself into a debugging hell where you could have rewrote the method by the time you solve it

[@zauberfrosch11]

I only watched through the basic explanation, because I forgot how binary search worked in principle. Really nice way of explaining and I also like how you explained the meaning of the log(n)

[@jonsnow9246]

Liked the way you handled the overflow. :)

[@saniyakhan9989]

i love how you made it look so freaking easy.

[@hernanphillip334]

It's so clear and well explained, thank you ma'am

[@bimgonzaga]

Great explanation! Thank you! But if you are searching a number bigger than your maximum element in the array, it will through a ArrayIndexOutOfBoundException. We need to cover that edge case with: if (left > right || right >= array.length) { return false; }

[@miguelarce452]

I was making this mistake at first, I was passing "array.length" on the initial function call then I realized that you have to pass "array.length - 1" instead. Then there's no need to add that extra check.

[@latedeveloper7836]

4:10 nice tip on how to avoid overflow error in Java.

[@goodwish1543]

Thanks for professional knowledge sharing. Why we need ``` while (left

[@Manu-wb2uv]

You won't be able to check the last element. Take this array for example [1,2,3]. You're looking for 3. First iteration: left= 0, right= 2, mid = (0+2)/2=1, is 3=2 ? false, is 3

[@pankaj3746]

I wish there are more women in IT! More power to you Gayle, you're doing a fabulous job!

[@muchen303]

That while condition left

[@omarmalik5099]

I think you meant left -1 < right

[@rolandovillcaarias5112]

Thank you so much, what font are you using in the Eclipse Editor please. It looks comfortable for my eyes.

[@kitchiong2861]

Thanks for the awesome video. Just one question that I can't wrap my head around, can right start with arr.length instead of arr.length - 1? Is there any counterexample? Thanks!

[@Aliennnaa]

in most programming languages array starts from 0 , so for an array of length =n the last element will be at position n-1 meaning at arr.length-1 so no you cant start right with arr.length

[@dijoxx]

Arrays use 0-based indexes in Java. So arr[0] refers to the first element of the array. Following that logic, arr[arr.length - 1] gives you the last element.

[@sanjsin]

Pretty simple explanation of binary search, i studied this in 1992, visited this link to explain my highschooler daughter for ap comp science.

[@ashwinipowar2230]

Mam ,if the elements of array are not in a sorted order(for binary search) then we should make it in sorted order and solve the question or we cannot apply Binary search for unsorted elements?

[@roman3249]

This implementation doesn't work if the array has repeated elements though. It should be slightly changed for that situation.

[@SnowDragon894163]

changed how?

[@quentinz6291]

1:35 "must be sorted", yeah, that's why inOrder traversal is important in a BST

[@LokeshBarla]

Thanks so much.... It's simple and sweet when explained this brilliantly.

[@ngoviethung801]

Very informative, straightforward thank you

[@richashalini1068]

Wow, such am amazing explanation Gayle

[@Bee4Brendan]

Now that I explained it in a decent manner, let's make it confusing just in case you understood it.

[@amy-cx9ok]

hahahahha

[@hakami1426]

Is left and right the indexes themselves or the values?

[@wenjieyu6242]

Thanks! The presentation is really nice, easy to understand and very clear!

[@FLYAEROBOY]

if (left > right) { return false; } What does that even mean? Assuming it's a Sorted Array, how will left > right ?? Can you someone explain what she means by the first if( left > right ) statement

[@mohammadhanifahnurshafrudi8208]

maybe its to check the array is sorted or not .

[@floatingscrib]

That if statement essentially checks if int x is not in the array. Remember that the integers left, mid, and right are indexes for the array. Lets say that left starts out as 0 and right is 24. This puts mid at 12. Lets say int x is smaller than array[left]. This would mean that x is smaller than array[mid]. Under recursion or iteration, right will be come mid-1, which is 11. Mid therefore becomes 11/2 = 5. becomes Repeating this loop will still show that x is smaller than array[mid], considering that it's still smaller than array[left]. Therefore right becomes mid-1 again, aka 5-1 = 4. This will continue to repeat. Mid becomes 4/2 = 2, and right is 2-1 = 1. Mid becomes 1/2 = 0, and right becomes 0-1 = -1, making left > right. We can do this in the opposite direction where x is greater than array[right], which progressively increases left . Going through the loops, with mid at 12, left will be 12+1 = 13. This will put mid at (13+24)/2 = 18 and left as 18+1 = 19. The next loop will be mid at (19+24)/2 = 21 and left at 21+1 = 22. Then, mid is (22+24)/2 = 23 and left as 23+1 = 24. Finally mid becomes (24+24)/2 = 24 and left is 24+1 = 25, making left > right.

[@dhavalsoni9941]

Any time, Left > Right means, Array is not sorted so not to proceed with. As this technique on sorted array only. If array is not sorted or rotated then, its other way around to go with Divide and conquer (quick sort) approach.

[@HugoAyala1983]

Great explanation and examples for recursive and iterative approach!

[@aniketmasram6500]

I wish I had a teacher like you 🙂🙂

[@MinisterGold]

Zach... that detached head... just caught me off guard.

[@PrincessSarahjayne11]

Great video, made that very easy to understand !

[@JamesBrodski]

Great video! Thank you so much. I finally understand.

[@srinivasadineshparupalli5139]

Hi, Can you please let me know what is the algorithm name which does all the binary tree operations(like breadh-first, preorder, inorder ets). thanks.

[@syedahkam7164]

well this is easier than i expected it to be

[@haneulkim4902]

1. how does computer pick its mid point? 2. when there are two elements left, which one does it choose?

[@Breakout1345]

Answer to 1 : midpoint is chosen by (left + right)/2; Answer to 2: it chooses the 1st element (n/2 = floor(n/2) by default)

[@haneulkim4902]

@@Breakout1345 Yes, I was just confused because I didn't know low,high refers to index, not the element value.

[@lemardyc]

I am a teacher and if I was searching for Zack (are they really sorted by first name?), I would do a linear search from the back.

[@olorinorphique]

Ok what if all your student's first name start with a Z or a Y . And you have 3000 students. You picked the best case scenario. Big O notation is all about the worst case scenario. In my case, which is worst case. Binary LogN is still a lot faster than your linear from the back of the stack search. Peace.

[@irwingoh94]

Did Zack do something wrong? Why do you need to find him?

[@RussTeeTrombone]

That's why you're a teacher and not a software engineer

[@thorn8485]

If you know something about your data, that's great. Algorithms are for the general case, when you don't know anything super specific about your data and you always need to return the correct answer, i.e all you know about what paper you're looking for is that the name starts with A-Z and that the papers are sorted alphabetically.

[@eduardodelgado7873]

Linear search hmm what if it's not in sorted in order 😂

[@marq_8976]

Excellent explanation.

[@Vibestr]

For the recursive example, anyone know why she two of the same methods (binarySearchRecurive()) with different number of parameters? That's kind of confusing. Also how would the program find the midpoint if we are dealing with an array with 10 items? Would it round up to the 5th index?

[@RRWX]

Now i know every thing about coding!

[@shahabyaftali3848]

for a couple of seconds i though i lost right side of my headphones XD

[@veraqiu6734]

hey there, can you explain why we put (left

[@siobhanahbois]

You won't be able to check the last element. Take this array for example [1,2,3]. You're looking for 3. First iteration: left= 0, right= 2, mid = (0+2)/2=1, is 3=2 ? false, is 3

[@oln1908]

Me taking notes of binary search only to be distracted by that satisfying keyboard click

[@manoelramon8283]

left+((right-left)/2 still can overflow

[@wonimpty]

what if its even number and you cant find the median(the middle number of the array)?

[@FuzzyDPozzy]

The tutorial was good till 2:40 , then you show up code and I wasn't able to understand anything unfortunately. However I do know how to do this on my own which I will do, but this was a while back so I can understand. All I am saying this could have been implemented and understood easily if only the structure of the code was better and more importantly simpler.

[@stevenshrii]

With no duplications of elements the array

[@josealb2]

The iterative version implemented at the end returns true and false but should return the index

[@asero82.]

Both versions returns a boolean meaning what your searching for is or not in the array

[@bitti1975]

Why not (left+right) >>> 1? It's shorter and faster

[@goodwish1543]

谢谢大师分享，请问这里为什么需要小于等于 start

[@leomonz]

The coding is very confusing because she was not doing actual coding, just abstract coding there..... Although abstract coding is fine but really confuse people who trying to follow as they haven't done it before

[@ahmadalalwani5176]

thanks for confusing

[@viddusliteracy9087]

Ahmad Al Alwani hehehehe hahaha..for me to

[@ton_]

@@123214matt then don't watch, noob

[@paulvincentdesamparado5817]

how to run the recursive implementation code ????

[@NachiketJoshiTheBloodMage]

why one of the parameters of binarySearchRecursive is (array.length - 1) and not (array.length)?

[@patrickvanvorce2670]

To add on to the 0 indexing, that last element in an array is null, so when she says array.length-1 it is making sure it is accessing the last data input and not the null char.

[@lethanhan9084]

anybody know why: 1. the top pointer need to be inclusive 2. when replacing low and high, it will be mid + 1 and mid - 1 respectively?

[@thatoneuser8600]

Idk what you mean by 1, but for 2: Because if we don't do that, then we rely on the 'mid' variable to solely push us to the base case, which can lead it to get stuck due to the rounding down when dividing, and thus, receiving a StackOverflowError if the target is the very last number of the sorted dataset. No matter what, it will never be able to reach the last index since odd + even = odd, and divided by 2 where it rounds down would equal the smaller (left) integer of the pair, creating an infinite loop.

[@farahizzati5676]

THANK YOU SO MUCH I TOTALLY UNDESTAND IT NOW:)

[@Stealth7596]

what is the difference between (left + right)/2 and left + ((right - left)/2) ?

[@munnat8073]

to prevent overflow in java

[@EnriqueMoranG]

Thanks ma'am

[@anshitkumar6347]

The vocal fry's too strong here

[@Caldera510]

Very nice! Thanks!

[@sampurnanand3379]

what are the time complexities of iterative and recursive versions?

[@sampurnanand3379]

And also the space complexitites

[@SathishKumar-yw4qs]

Can u say what is the software u r using.....

[@makii1715]

I know this is like 10 months ago but if you still want to know : probably Eclipse

[@warnercooler4488]

Thank you so much!

[@faisaladil5793]

excellent work.

[@christopher5731]

These videos are usually pretty good. This one... not so much

[@MrDeeb00]

Brilliant Thank You! 🌹

[@CristianMihalyi]

Why could it overflow if (left+right)/2? The mid position is always in the array, isn't it?

[@VS-ey2lf]

+Britka sablja Thank you so much for the explanation!! I was wondering for an hour why is it like that.. Thanks again

[@philtrem]

It's got to do with the max value a given integer type can hold, not to be confused with index out-of-bound errors.

[@RABANAND]

But the value will be assigned to the variable after the division of 2 right. So in this case , How overflow is going to happen?? Please clarify

[@dk-sky3820]

Anand R (left + right) is stored in temporary int (behind the scene) to be divided. If it's more than 2^31 you're toasted...

[@irasanchez1265]

Thank you for making this!

[@mathiasyeremiaaryadi9097]

Why right is mid -1 ? why not mid + 1??

[@kenocvr]

Binary Search is cutting down the problem space (where to look) at every step in the algorithm. Right is on the "right" side of the array (at the end position). Left moves toward the mid (goes right) and right moves toward the mid (goes left). There would be no reason to increase the right position. Just like there would be no reason to decrease the left position.

[@Yilz19]

Shoutout to all ma procrastiboiis

[@benito2056]

Nice.

[@shamsansari]

why is the method a boolean, shouldn't it be int?

[@tugcehilal2536]

it returns true if it "finds" the element. this is a search algorithm

[@Ishaaq92]

where did Andrew come from?

[@supergoodwhite]

does anyone have any answers for Challenge: Binary search

[@vladimir781]

int mid = low + ((high - low) / 2);

[@skril733]

int mid = (low + high)/2

[@irynaprokopenko6438]

Vladimir, yes, correct

[@yoowon-hye9270]

Or ((high+low)/2)?

[@reshmayasmin9717]

Can we do it with for loop?

[@robbeandredstone7344]

Yes you can, just do for(int i = 0; i

[@gabrielpereiramendes3463]

Very Good!

[@a.d.477]

made a confusing one hour lecture make sense in 6

[@irinish]

what if there were 12 numbers instead of 11? What would be the mid then?

[@thisisbob1001]

Good question

[@yoowon-hye9270]

For arrays of even lengths, the midpoint index will always be the quotient of array.length/2. In your case, someArray.length -> 12. Thus, mid = someArray[6].

[@yahyahassan7499]

Is it my school or something I'm 12 and have a test on this tommorow these grades will determine if I have dropped or grew from last term 1 like 1 prayer I will pass

[@nicholasfurlonger8796]

i hope you failed yahya

[@ng4logic]

Yeah every 12 year old should know binary search

[@good_life_videos]

recursively and irr... what? 5:55

[@theguardianarchives433]

Iterative

[@sandeepmehra5760]

BEST VIDEO

[@ryn0904]

This just confused me even more

[@benmiles1505]

I doubt that there are many names that come after Zach so you shoud just go to the end and work backwards. smh my head

[@thecandel5479]

Very nice! 🌹

[@nadiasd5914]

good job! very good explanations>

[@cuiatk9492]

How to Dry Run The Recursive CURSE! My Brain Cells are Dying.!!

[@danval407]

I'll have the coffee shes drinking

[@Jonathan-od5xc]

dan val LOL

[@mathaalbhai]

This is one most confusing binary search for beginners!

[@praneelmadhuvanesh3770]

wtf is the point if the arrya has to be sorted. that means u must have already found the thing before

[@zombie8956]

Just because it's sorted doesn't mean you have O(logn) lookup automatically. For example, if I asked you to guess a number between 1-100, would it be faster to go through every number or to start at the mid point, ask if its higher or lower, then create a new midpoint?