Binary Search - CS50 Shorts

No video

Binary Search - CS50 Shorts

Рет қаралды 128,301

Күн бұрын

***
This is CS50, Harvard University's introduction to the intellectual enterprises of computer science and the art of programming.
***
HOW TO SUBSCRIBE
www.youtube.com...
HOW TO TAKE CS50
edX: cs50.edx.org/
Harvard Extension School: cs50.harvard.e...
Harvard Summer School: cs50.harvard.e...
OpenCourseWare: cs50.harvard.e...
HOW TO JOIN CS50 COMMUNITIES
Discord: / discord
Ed: cs50.harvard.e...
Facebook Group: / cs50
Faceboook Page: / cs50
GitHub: github.com/cs50
Gitter: gitter.im/cs50/x
Instagram: / cs50
LinkedIn Group: / 7437240
LinkedIn Page: / cs50
Reddit: / cs50
Quora: www.quora.com/...
Slack: cs50.edx.org/s...
Snapchat: / cs50
Twitter: / cs50
KZfaq: / cs50
HOW TO FOLLOW DAVID J. MALAN
Facebook: / dmalan
GitHub: github.com/dmalan
Instagram: / davidjmalan
LinkedIn: / malan
Quora: www.quora.com/...
Twitter: / davidjmalan
***
CS50 SHOP
cs50.harvardsh...
***
LICENSE
CC BY-NC-SA 4.0
Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International Public License
creativecommon...
David J. Malan
cs.harvard.edu...
malan@harvard.edu

Пікірлер: 61

@GY-yv5cz Жыл бұрын

Probably my favourite algorithm. Any time I know a dataset is sorted, I just want to employ this.

@troyke 4 жыл бұрын

Thank you Doug! As always, a very clear explanation, with visuals to help support your points!

@omaroats 6 жыл бұрын

Perfect. This was well explained and easy to follow. Thank you Doug ❤︎

@codeklaudia9696 2 ай бұрын

Thank you for the video :) Sometimes it is hard to find the Middle. In Python 2, all sorts of divisions return an int. In Python 3 we need to use the // operator

@candicehwt6375 3 жыл бұрын

every time he asked a question, I was like no please don't pick me to answer, I don't know

@mandaleswaranthasarathakum3130 4 жыл бұрын

Thanks man helped with my computing test on search and sorts

@hugger-bd5ij 4 жыл бұрын

Matthew Mcclintic why

@vk-hm6te 4 жыл бұрын

@Matthew Mcclintic why

@MR0IAM0WATCHING0U 4 жыл бұрын

@Matthew Mcclintic why

@matthewmcclintic5488 4 жыл бұрын

Sorry, I don’t know why I said that. I was trying to be funny next to my friend, as you can see with other comments, but it was stupid.

@matthewmcclintic5488 4 жыл бұрын

I thought the video was very helpful too and it was not my place to say something like that.

@whatever63644 4 жыл бұрын

I have a question, what if the number of elements in a sub-array were to be an even number instead of an odd number? Do I round it or just take the integer part?

@user-kr9wx5of8j 3 жыл бұрын

@@kariimnabiil-911 when the number is 5 the middle ==3 in humanity but in code from 0 what I do when the number is big and I don't need code you understand me, please If you understand, please reply me.

@julianarchila3671 3 жыл бұрын

You use a round function

@alialparslan2288 2 жыл бұрын

I think it is up to you. It can be a round function, you can take the int value, or you can look through the middle two number separately ( it will not be the best design, but it's possible) or any other idea. The key is finding the best approach. And i guess, your suggestions are good enough

@mohammadkermani2987 4 жыл бұрын

Awesome! It was a pretty simple explanation and easy to understand. I enjoyed the way he was explaining in detail and showing it visually! thanks a lot

@ktswjp 4 жыл бұрын

Great job, Dough! Keep it up. You divided this problem to as simple as possible chunks.

@ilyesbenmalti9402 2 ай бұрын

How's life bro

@TheInvestmentCircle 4 жыл бұрын

I wish there were coding examples in these videos :[

@Dinopeach 4 жыл бұрын

check big-o.io

@exnihilonihilfit6316 2 жыл бұрын

Ever heard of Google and Wikipedia?

@ojalafsenior4757 Жыл бұрын

Very well elaborated Doug

@LoneWolf5960 6 жыл бұрын

I'm still trying to wrap my head @7:33 how does the looping logic turn to "Repeat until the (sub)array is of size 0" based on the upper right hand table in the corner. What does "(sub)array is of size 0" mean anyway?

@kitpaovm8537 4 жыл бұрын

when start point is greater than end point, you can inffer that the subarray is size 0

@sithoidinh3891 3 жыл бұрын

Binary search is much more better than linear search!!!

@deronburton2994 4 жыл бұрын

Does it only work with a linear arrays?

@swanandpangam 6 жыл бұрын

But why doesn't we calculate the sorting time as it is the necessary prerequisite?

@abhinvra 6 жыл бұрын

Binary search is used only for sorted arrays.

@abhinvra 6 жыл бұрын

It's not a sorting algorithm but a searching one.

@abhinvra 6 жыл бұрын

For example you can make use of a sorting algorithm such as Merge sort to sort the array and then use Binary search to find if an element is present in there.

@jayant9151 6 жыл бұрын

ajfjeoaiodjkajgd report

@andreasv9472 2 жыл бұрын

Because they are two separate operations. Maybe you make thousands of searches for each time you make a sort. In practical terms, if you have sorted one billion webpages (if you are google for example), then you only care how quickly you can give search results to the user. You do not sort the webpages each time someone makes a search on google. You sort them once in a while, and then you allow maybe millions of searches on that array until the next time you sort it. So the speed of the search is what matters here, not the speed of the sort as it is likely to be done in advance, and only once in a while.

@atalaguitare13 6 жыл бұрын

Awesome !! Continue guys !!

@random-xl3zm 8 ай бұрын

odin project ? lets do it hare krishna

@mortimerc317 Жыл бұрын

thank you

@user-nl8wi2cg9x 7 ай бұрын

Great content

@theorbit17 6 жыл бұрын

my mans

@xxRuleZzZxx 3 жыл бұрын

@Matthew Mcclintic le mans 24 hrs

@maxim5519 Жыл бұрын

thanks!

@LUITEN1 4 жыл бұрын

Would someone elaborate on the Log n part? Why doesnt that log have a base? I get that as long as n increases, so will the lenght of time (in the linear search case) but I dont fully get it..

@callumross7682 4 жыл бұрын

In math you tend to presume the base is 10 if it is not given

@exnihilonihilfit6316 4 жыл бұрын

If you go two thirds down this page to the section entitled _"But Sometimes There Is Confusion ... !"_ , you'll see a little discussion of it: www.mathsisfun.com/algebra/logarithms.html But in this case, the base is 2. n=1 log[2](1)=0 n=2 log[2](2)=1 n=3 log[2](3)=1.58496 n=4 log[2](4)=2 n=5 log[2](5)=2.32192 n=6 log[2](6)=2.58496 n=7 log[2](7)=2.80735 n=8 log[2](8)=3 n=9 log[2](9)=2log[2](3)=3.16992 David Malan talked about it in the lecture (link has timestamp): kzfaq.info/get/bejne/nN-bpc-ix7ydp4E.html

@elia552 Жыл бұрын

@@callumross7682 for anyone else reading this now, in computer science you presume the log to be 2, NOT 10

@kieffel7013 Жыл бұрын

@@elia552 thanks! if the size of the array is 15, in the worst case scenario it should take 4 iterations right?

@elia552 Жыл бұрын

@@kieffel7013 honestly I stopped learning coding and computer science and this is gibberish to me

@sakib2249 2 жыл бұрын

what if array size is 15.

@TheThirdlevel-un8do 9 ай бұрын

Nice teach you

@TheThirdlevel-un8do 9 ай бұрын

Nice sir

@krupasankari 5 жыл бұрын

Doug Lloyd really looks like Doug Mcquaid lol

@nurgisaandasbek 4 жыл бұрын

Super!

@samuelfey4924 4 жыл бұрын

we go to the middle I understand that perfectly but how do we chouse either right or left? cause we dont know where that number .

@alim.7841 4 жыл бұрын

Binary search algorithm works for only sorted arrays so if you find in the middle number less than your target you have go right because there you will find bigger numbers, watch this 0:30