Binary Search - A Different Perspective | Python Algorithms

[@Mutual_Information]

Can’t overestimate how important it is to know this for coding interviews.

[@mCoding]

Being able to explain is sometimes just as important as being able to write it!

[@khappekhappe133]

give an example please?

[@Mutual_Information]

​@@khappekhappe133 Find the 'pivot position' of a rotated sorted array. That one jumps to mind.

[@mohammedj2941]

can’t overestimate* 😁 sorry for the pedantry but I agree with your point

[@Mutual_Information]

@@mohammedj2941 gah! thank you - corrected!

[@Simon-fu8sd]

I'm so happy that I found this channel. I can watch something that is interesting and actually important for my studies

[@mCoding]

Welcome aboard!

[@Y2B123]

Exactly. There is no bullshit or drama here either. Just fun in coding itself. Wonder why he doesn’t get more subscribers.

[@sjeff26]

I'm preparing for a coding interview and think that this is a great explanation. It's a lot simpler than many of the implementations out there online and a lot more intuitive as well.

[@Alister222222]

It's funny how instead of clicking 'like' once, I click it like 3 times now for these videos

[@mCoding]

A true fan!

[@GeeTransit]

i slap it four t y one times :P

[@NaifAlqahtani]

@@mCoding you mean True*

[@laurinneff4304]

@@NaifAlqahtani true, false = True, False

[@haibai1766]

Thank you for actually going over monotonic functions, they're much more widely used than just binary search on an array alone.

[@mCoding]

I always think about it as std::partition_point from C++

[@Maurycy5]

I lead algorithmic masterclasses for high school youth and although I personally use a different implementation I must say - this video is very high quality! I am very impressed. I was ALMOST convinced to start using this implementation, but you aren't getting me this time!

[@mCoding]

Thanks for sharing! Maybe next time!

[@xakkep9000]

I suppose different algorithm keeps lo at true value and hi at false value. Also it didn't use an increment of mid index. And finally different loop condition stops exactly at lo=1+hi. P.S. lo initialized by -1 😉

[@drishalballaney]

FINALLY the video I want! please do more of these kind videos related to algorithms, sorting etc

[@mCoding]

Sure thing!

[@Ovicron]

+1 to this

[@monkeecrap]

I appreciate the depth with which you covered this topic. It shows how to view the algorithm from a perspective other than just “memorize it”. Thank you!

[@mCoding]

Glad you enjoyed it!

Never thought the meaning of search could be ambiguous in binary search. I always thought of me searching for a number, it's interesting to think about that the search can be to where to place that number. Once again great video always to the point and very precise and clear.

[@mCoding]

Thank you!

[@Doodle1283]

What I love about this channel is that every video gives me at least one insight about the topic.

[@mCoding]

Thanks so much!

[@geansantos9968]

THANK YOU VERY MUCH: I tested it by making an array with 10million numbers, it found the number wayyyyy faster and only with 25 iterations rather than the 10million the normal code would need.

[@jhonsen9842]

I think i am bit Late to your Channel but its better late than never. Someone pointed me in Medium to your channel and he wrote that this vidio changed his way of think in Binary Search. I think he was right. Its really intuitive way of teaching.

[@feerasse9931]

It's still difficult to wrap my head around genearting Binary Search, but this is the closest I have come to deeply understanding the concept. Thanks.

[@abdulmasaiev9024]

"But, the array being sorted, I claim is actually not the property we're using here" -> proceeds to use the property that the array is sorted with regards to (lambda a, b : (b < 7) < (a < 7)) as the comparator I have to disagree. You're still using the fact that the array is sorted, just not in the "traditional" sort. And the fact that the array we're usually binary searching through is sorted "traditionally" isn't usually used to enable the insertion of 7 specifically, but any number at all. The "traditional" sorted property of an array implies the (lambda a, b : (b < n) < (a < n)) sort for any arbitrary n (with the obvious caveats for "arbitrary") which is the sort that we actually need, and so we can run it knowing nothing about the array. Here we don't have that. Sure, it'll work for anything bigger than 5 or smaller than 4, but for instance where should you put in 4.5? And so without this "traditional" sorted property, if you insist on using binary search in it then for an initially unknown array dealing with these unevennesses requires introducing extra checks which put the whole thing into O(n), which defeats the purpose of using a binary search at all in the first place.

[@t_kon]

Yes the fact that you can use binary search as a general searching algorithm will ever only apply to a sorted list. This indeed is just fact. Came here looking for someone else that realizes this.

[@cottawalla]

@@t_kon ditto.

[@aman_mo]

Yeah, I was super confused when he said that the array doesn't have to be sorted. Unless, of course, he was willing to increase complexity to O(n).

[@jasonlowmiller9869]

Also came to the comments to see if anyone else is seeing this now as O(n).

[@rdwells]

Thank you for providing a video on binary search that is good enough to show my students. Extra points for pointing out the potential for integer overflow when using almost any other language. It may be worth pointing out that, bisect_left() and bisect_left() are the same as the lower_bound() and upper_bound() algorithms in C++.

[@mCoding]

Thank you for sharing my video with your students, and the cpp algos were indeed the inspiration for this video!

[@DjKryx]

I recently used binomial search for finding the cutoff value that minimizes the distance between specificity and sensitivity of a model. The brute force method, that calculated the values at 100k different points, took about a minute to run, binsearch needs 3 seconds

[@quillaja]

I recently did something similar with binary search for the altitude where the 3D surface area above and below that altitude are a specific ratio. It becomes a powerful algorithm when you realize it can search any "sorted" space, discrete or continuous, instead of just arrays.

[@khangtrantuan5377]

Thank you so much for the explanation. By my understanding, lo will be the first index that the condition is false, and hi will be the last index that the condition is false. So when the condition is true, we can directly update lo = mid + 1, because like you said, that might be the first index in which the condition is false. We don't update hi = mid - 1, because, when we update hi = mid - 1, There might be a case that mid is the first F, so we might miss that F, therefore the best we can do is update hi = mid.

[@davidhuang6549]

Man this is a great way of conceptualizing it and makes memorizing small implementation details so easy! Awesome content

[@MrRyanroberson1]

i found this right after successfully implementing basically that exact strategy at 4:40 to find the location of a cell in a 2d array. it is really really satisfying to implement even a simple search like this

[@tacokoneko]

7:45 to change your code to implement bisect_right() instead, replace lines 6-10 with the following: if arr[mid] > x: hi = mid else: lo = mid + 1 return hi

[@viktorstefanov4848]

this is pretty much the same thing as changing the if condition to if arr[mid]

[@radek2483]

Here is what I feel is even more intuitive, as it works with simple invariant. Set lo=-1 (one before array) and hi=n (one after array). Then I want to preserve this invariant: lo always looks at T and hi always looks at F. Because what I am looking at when doing bin search is neither the first F, nor the last T, but the gap. So i while (hi-lo>1) and look if mid is T, then lo=mid (because invariant) and if mid=F, then hi=mid. And when this algorithm end, it gives two pointers. one to the last T and one to the last F, hence giving the gap in between with full symetrical view. After that i can I can thing of what I really need in current problem. Do I need the first F?, do I need the last T? Can the asfer be after/before array? All of these are questions, that I solve after I get my bin search pointers :-)

[@linear9185]

I appreciate videos like these a lot as I don’t have any formal education w/ computing so basics like this are rlly helpful

[@mCoding]

You are welcome!

[@sampopaukkonen4014]

I can see from the level of articulation that you must have some mathematical background. You covered well all of the ifs and buts one raises when writing any algorithm, and actually gave a rigid proof for the validity of the presented bisection method! Hopefully this video will be used as "the" tutorial on bisection search in the future.

[@mCoding]

You are correct, I am a trained mathematician! Thanks, I hope so!!

[@memespdf]

These videos are great! The new mic is also very good

[@mCoding]

Yay, thank you!

[@yazanalj1975]

I'm currently learning about binary search and and other searching algorithms and this video definitely helped, thanks a lot

[@mCoding]

Great to hear!

[@heisthazey7311]

for bisect_right implementation (please keep doing more of these small quizzes/challs, i was watching the broadcasting video this past weekend and that one was fun to do) `````` def bisect_right(arr: list, x, lo=0, hi=None) -> int: hi = hi if hi is not None else len(arr) if lo< 0: raise ValueError(''lo can't be equal to the balance in your chequing account!') while lo < hi: mid = (lo + hi)//2 if x < arr[mid]: hi = mid else: lo = mid + 1 return lo

[@mCoding]

Good! I hope you arrived here by first simply replacing < with

[@asad-ullahkhan2368]

Great vid! Knowing when to use slice indices vs element indices is important for many problems involving arrays

[@mCoding]

Glad it was helpful!

[@TimBrownYoutube]

You can add the following lines after the loop to tell if value exists. if lo == len(arr): return -1 if nums[lo] != x: return -1

[@redactoboggy]

At 7:01 you add an assert statement. Worth noting that this is only executed when running in non optimized mode. A production ready implementation should rather raise a ValueError.

[@mkbr-yt]

Hi professional noob here. I just found out the traditional binary search does not properly work for finding the first occurrence of element in a sorted list. Using the given example binary search insertion will do but will not guarantee the first index. We may or may not get the correct index. IT only ensures to INSERT an element at a position that maintains the sorted order. It is better to use linear search O(n). We can extend the binary search by adding these steps: (Sort of a race condition solution in React) 1. Using a flag variable to store the mid where the condition list[mid] == x is true. -> This is for occurrence that is in the mid. 2. Adjusting the hi to (hi = mid ) to continue searching for the first occurrence in the left side. -> This ensures to find earlier occurrences. 3. Returning the flag variable that holds the last occurrence in the left side(first occurrence) at the end of recursion / loop getting the benefit of O(log n). Binary search is use for sorted and unique list. Just sharing what I have learned for someone who is trying to find first occurrences and learning binary search to videos like this.

[@kashifahmed_1995]

Thankyou for this brilliant way of explaination and you also helped to look a problem with altogether new angle

[@mCoding]

And thank you for your kind words!

[@James-ml5mu]

My brain understand it better when i think of the if condition as x > arr[mid], idk why but thank you for this vid

[@EmadGohari]

this was a crystal clear presentation and thanks for step by step writing the code. please do more videos like these!

[@mCoding]

Sure thing!

[@Periareion]

This helped me make an algorithm to solve a similar problem! Thanks, James.

[@shivangyadav5887]

Left bisect concept is used to find Minimum time,Minimum Height questions using binary search.

[@berylliosis5250]

I'd argue that the true/false property is still "sorting", just using a different sort function. Perhaps sorting by that function may perform better in some scenarios though? An interesting idea

[@mCoding]

It certainly can be though of as being sorted with respect to a different sort, technically, but this scenario usually goes by the name "partitioned" rather than "sorted".

[@name1355_0ne]

Thanks a lot, James! Your explanations are awesome. One of the best Python related channels on KZbin. Subscribed with pleasure.

[@mCoding]

Thank you so much for the kind words!

[@ericyoung4542]

This is so helpful! I like your reasoning. Everything is well justified.

[@jianxiang]

The abstraction is gold.

[@mCoding]

Thanks!

[@Anamaya1729]

I was just studying this morning! Great video!!

[@mCoding]

Awesome! Thank you!

[@malayparmar504]

Please make more videos on Algorithms and Data Structures!!! Thanks for this video❤️

[@mCoding]

Sure thing! These take a loooot longer to make than the other videos though :( Glad you liked it!

[@michaelflynn6952]

great way to spend 4:20, thank you my bro

[@mCoding]

Took me too long to get this...

[@unclesheo1243]

@mCoding around 3:12 you say "I think that far too often, binary search is taught solely as an algorithm that works on sorted arrays. But, the array being sorted ... is not actually the property that we're using here." That's a pretty misleading statement. I think it does more harm than good, as you're confusing "the algorithm" with "the algorithm's behaviour on a specific input". Yes, strictly speaking, the property we're using is: "only the elements that we visit need to be sorted". But exactly which elements you visit depends on the input. In order for the algorithm to work for ALL inputs, the WHOLE array MUST be sorted. Try finding an 8 in your second, no longer sorted, array. You'll land on the 9 instead.

[@mCoding]

If you knew that you were always going to search for 0, say, then you would not need the array to be sorted. The sorting requirement comes only from the fact that you do not have any extra information about your input. The real precondition for bisect(arr, x) to work (this implementation at least) is not two separate conditions on arr and x, it's a joint condition that arr is partitioned wrt x. This is the property that is actually used in the algorithm and the property that helps you remember the implementation. Saying arr needs to be sorted is only a practical convenience to ensure that your array is partitioned wrt every element. The most common use case of course requires the array to be sorted. But if you really want to understand the algorithm and its true limitations, you need to drop that crutch. Bisection works in a much more general context than even 1D arrays, I may talk about its use in mathematics in the future, e.g. in random number generation or a proof of the intermediate value property of continuous functions on intervals.

[@unclesheo1243]

@@mCoding Thanks for the answer, although I'm even more confused now. If I knew I was always going to search for 0, why would I search an array of numbers rather than keeping track of the count of zeros? If the array was the result of some other computation, which only guarantees it's partitioned wrt 0, then yes I could binary search for 0. But why should I? That other computation certainly knows where and how many zeros there are, right?

[@wassimhaimoudi]

I see your point but hypothetically is a sorted array really a sorted array if you are if you are going to continuously try to add elements to it that are yet to find their order in the chain. He is assuming that the element is already there in an implicit way even though its not. Or rather tries to find its location based on a new perspective which only depends on a sorted portion. Not the whole. Here is how i imagineds it. Imagine you have an array of infinite numbers and the target you have "should" take place at the "end" yet the array is infinite how do i know the rest is hypothetically sorted? This approach solves that by ignoring whatever after the firsr occurrence of the target since we are going to reduce the hi pointer anyway to it to at most fit the size - 1 of the array tangibly.

[@brunoberganholidias5790]

Correct me if I'm wrong, but I think there is a typo on line 2 at around 7:00. It should be hi = high if high is not None else len(arr) Either that or changing the argument name "high" to "hi", although I'm not 100% sure this would work.

[@mCoding]

You are correct, thank you for pointing this out! The parameter name was supposed to be "hi" not "high"!

[@mCoding]

I went to go and fix it in the code but it was already fixed! I used the wrong take in editing!! Sorry for the mixup.

[@brunoberganholidias5790]

@@mCoding No problem. It was just a tiny mistake and overall the video was great! Keep on pumping out great content!

[@PetrSUsername]

I was gonna write the same, plus: I believe you can simply write: hi = hi or len(arr)

[@mCoding]

@@PetrSUsername In this case you can't write hi = hi or len(arr) because what if someone passed hi=0? If you used hi = hi or len(arr), this would throw away the upper bound! I know it is inconvenient to use the longer None check, but it should be preferred in most cases because of tricky situations like this!

[@maxteer2800]

Love that you are improving your recording. This is much easier to read. =]

[@mCoding]

Yay, thank you!

[@officialbfi01]

Great video as usual 👍 I’d be really interested to see you go through a merge sort algorithm because I find them very hard to understand logically. I understand that you split the components up and reorder them in increasingly larger groups, but I don’t understand where the efficiency of it comes from because it seems like there are still a lot of steps. Maybe that’s just me though! Anyhow, if you DO do some more videos on sorting algorithms I’d be really interested to hear your explanation of a merge sort, you have a good way of explaining things.

[@mCoding]

Probably will!

[@RuslanKovtun]

"slap like button odd number of times" very precise

[@infusion5943]

I like to do it recursive and use it with a wrapper method. in Java for example: public static int bin_search(int[] arr, int start, int end, int numToSearch) { int mid = (int)((start + end) / 2); if(arr[mid] == numToSearch) return mid; return arr[mid] < numToSearch ? bin_search(arr, mid, end, numToSearch) : bin_search(arr, start, mid, numToSearch); }

[@Abhishek-fe3zs]

Very, very useful. Thank you.

[@will5x]

2 words for you, my friend... Thank you!

[@mCoding]

You are welcome!

[@lets225]

Meguru-style binary search is the most bug-free implementation.

[@josht7238]

thankyou so much for this great explanation

[@jullien191]

설명이 진짜 좋아. 고맙다^^

[@sapito515]

new mic is awesome!

[@mCoding]

I think I'm getting the hang of it! It turns out I had a lot to learn about audio production, the mic was only half the problem!

[@rachitrihar4034]

Great content. PS: This guy doesn't blink

[@mCoding]

Huh... I never noticed! Should I purposefully add blinks in to make people feel better?

[@rachitrihar4034]

@@mCoding no! Just present in the most natural way you can. That blink thing was just an observation.

[@emilkondov5120]

What is meant by "Overflow"? Why it is not while lo

[@mCoding]

Overflow refers to the result of a computation being too large (positive or negative large) to represent in the given data type. For example, if you are using 32 bit integers, x and y can be small enough to represent but x+y might overflow. So (x+y)/2 might not give you the average or of x and y even if x and y are small enough to fit in 32 bits because of overflow. Checking if x == mid first could give you a shorter execution, but it could also give you a longer execution because it is now an extra step you have to do every iteration.

[@emilkondov5120]

Thank you, now I have something to think about. Cheers@@mCoding

[@carlosffm]

Yes, this is technically a solution, but saying that "returning the position where you would insert the first one" is actually problematic in some situations and that's why you usually take formal classes to understand what to do when, not to mention you will most definitely find requirements for exceptions where no X is found. There is no magical implementation that solves everything. Also, there is a huge problem with the whole return the index where the first X would be inserted deal: say you want to find 7 in [8], you would get 0, sure, but does that mean there is a 7 or not? If you don't know the content of the list/array then that first element can be what ever and you would still get 0. It obscures a lot of information.

[@rohithkumarmiryala2083]

that's why there is an extra check at the end to compare whether the value at returned index matches the required value. This might be an extra step, but it removes a lot of complexities if you want to find first value, last value or find index where to insert which is very confusing if you go by normal binary search.

[@dlf_uk]

This code is certainly valid for the implementation described, but if you gave someone a binary search function that was returning indexes in the middle of a list due to that being “where you would put it”, even if there’s no matching element, I feel like that would cause massive confusion, and you’ve thrown away a huge part of the semantics and use of binary search, just to save yourself having to handle the case where the searched value isn’t present?

[@mCoding]

If course we don't want to change the semantics from a yes no to an index for existing code, rather im suggesting to change your perspective of binary search from a yes no question to an insertion index question. Given the insertion index version, it is a 1-liner to create a wrapper that returns yes no, just check if the index is in bounds and has the element you are searching for. All outside code can then continue to use the yes no version, while you can maintain the easy to understand and remember implementation under the hood.

[@dlf_uk]

@@mCoding I guess that makes sense. What's the beneficial use case of knowing where you 'would' insert something but not inserting it?

[@volbla]

Huh. When i tried writing a binary search i only kept track of the "middle" and tried moving that in the appropriate direction. It got too wonky to keep track of how big the next step should be and what to do with odd-number intervals, so i never got it to work. This makes a lot more sense.

[@JonnieZuramski]

Love the videos James, very good explanations.

[@mCoding]

Glad you like them!

[@pietervanoostrum1695]

Great explanation!

[@angelinazhou667]

If we use while lo

[@tincho15neem]

Extra points for type hinting.

[@paveltiurin436]

Hello, Great lesson, thank you. However, what I do not understand is: hi = hi if hi is not None else len(arr) statement. Looking at your bisect_left function I don't get where the hi value is supposed to come from if function doesn't take such argument. Do you have it assigned globally somewhere above? If not -> hi is referenced before the assignment here, isn't it ?

[@mCoding]

The function argument was supposed to be named hi as well, not high, sorry for this typo. The purpose of the statement is that if the user does not pass in a bound for hi, then the end of the array will work as an upper bound, otherwise use the bound the user passed in.

[@leandrormor]

this is brilliant

[@NyiajNtajVaj]

You should have been my professor 30 years ago

[@happyhacker4737]

Thank you very much!

[@wayneqwele8847]

This is awesome, thank you for making this video..

[@mCoding]

My pleasure!

[@oleksiihurov]

Does builtin bisects work with floats?

[@mCoding]

Yes! It works with any type that has a

[@aditya95sriram]

Very useful, thanks!

[@mCoding]

Glad to hear that!

[@hamol3d]

Excellent Video!

[@mCoding]

Thank you very much!

[@MrSteini124]

Fantastic content as always

[@mCoding]

Much appreciated!

[@julian____6509]

Thanks a lot for making this video

[@mCoding]

And thank you for watching!

[@expansivegymnast1020]

Great video!

[@Roger-xb7gg]

This guy is like the Nick White that isn't a poser

[@DSAGrindTime]

nah fr

[@AsifSaifuddinAuvipy]

Fantastic

[@afzalh07]

5:48 Can you please explain why fits false value couldn't be later than mid ?

[@mCoding]

In that case, the value at mid is a false value. The first false value cannot be later than mid because any later false value would be strictly after the one at mid and hence not the first one.

[@jullien191]

Por que el while lo 1: lo = mid, hi = mid

[@HousedHorse]

Would you mind sharing what colour scheme you're using in your editor?

[@mCoding]

Darcula, the default dark theme in pycharm.

[@breddy5215]

I am v confused while writing Binary search algorithms. I keep messing up whether to return left, right or mid, whether to use left

[@MazharSekunda]

Yeah, I suppose it can't find edge values of the lists when I write low

[@k5lre8]

At 6:56 Line 2 should be hi = high if high is not None else len(arr)

[@mCoding]

See the erratum in the description!

[@k5lre8]

@@mCoding oh that also fixes it

[@k5lre8]

@@mCoding btw, Great video very informative

[@michaelmalter2236]

Hey, how about discussing the square sum problem next? I find this one quite interesting.

[@abruptcall]

This is a crystal clear explanation!. thanks a lot. I can't help subscribe this channel haha

[@mCoding]

Welcome!

[@Angel33Demon666]

And what if the array doesn’t have to be an integer?

[@monochromeart7311]

Shouldn't you add a check for if the value doesn't exist in the array? Should just be that the loop ends at log2(len(arr)) iterations

[@mCoding]

This is not necessary since the answer we are returning is where to _insert_, which makes sense even if the value is not in the array.

[@monochromeart7311]

@@mCoding understandable. I usually return a -1 (or optional) in such cases because it can't be used as an index on an array. I'm aware of Python allowing negative indexes, but I program in C/C++. Overall to me it seems like better practice :)

[@TimBrownYoutube]

Had same confusion. Didn't realize function was returning insert position. You can add the following lines after the loop to tell if value exists. if lo == len(arr): return -1 if nums[lo] != x: return -1

[@aqworldsmaster88]

I love you, great video

[@mCoding]

Thank you again for watching!

[@HansLemurson]

I remember struggling when I realized I wasn't sure how missing entries should be handled.

[@mCoding]

A common struggle!

[@masheroz]

So essentially, you differentiate between the search, and the returning of the index to deal with the exception.

[@learner_1228]

Great sir, I have a doubt, sometimes we return l, h or store our ans, Sometimes l

[@shivamjalotra7919]

A problem that uses binary search the answer could be the next video to explain the usefulness of this algorithm.

[@mCoding]

I already made a video about a problem using it! kzbin.info/www/bejne/hHrMiq2geLOUmqs It's a long one though.

[@shivamjalotra7919]

@@mCoding Yeah LIS is a great one.

[@heads-up6704]

github repo for the code? :)

[@LxAU]

3:11-sorry, what? If the array is unsorted as [2, 3, 5, 4, 6, 9, 8, 7], then how would it find the 7?

[@mCoding]

The key property needed is that everything less than 7 is to the left, and everything bigger than 7 is to the right. Your array does not satisfy this constraint.

[@LxAU]

Ah, got it. You did say that. Thanks for engaging with me!

[@jensbang42]

@@mCoding : So what you're saying isn't that it doesn't have to be sorted. What you'rs saying os that it just have to be sorted in a different way. A binary search will not work on a completely unsorted array, which is what you're claiming it will in the video

[@azratosh]

Absolute wonderful video. I'm high as fuck and still understood everything very good

[@mCoding]

Check out my brownian motion zoom videos! kzbin.info/www/bejne/i4WacnpohNSMkNE

[@yuvrajpawar4177]

Mid = low + (int) ({high - low}/2) much better approach for mid,

[@moonkis9103]

Please, I need to know what font that is.

[@mCoding]

JetBrains Mono, aka PyCharm's default font.

[@spray5272]

doesn't this interpretation defeat a significant point of binary search - finding out whether a value exists in an array?

[@mCoding]

See the bisect_index_of at the end!

[@kartikjha833]

great video!

[@mCoding]

Glad you enjoyed it

[@Даниил-ц4э5о]

binary search can be written a little cleaner and simpler, without any + 1, and the algorithm, in my opinion, would be more understandable

[@mCoding]

You would run into an infinite loop if you didn't have the +1 here. Do you have an implementation that you could share?

[@Даниил-ц4э5о]

@@mCoding Sure: ideone.com/6i4x35 In that implementation indexes of elements, that are lower than x for sure, less or equals left variable.

[@Даниил-ц4э5о]

the only problem is that if x is greater tan every element in the list, this algorithm will return len(a) - 1. It assumes that the last element is bigger or equals, we can check that in the beggining, I suppose

[@mCoding]

You would additionally need to check the list is not empty so you don't return -1 either. But I think you can make it work. It's also not clear exactly what the loop invariant is in this implementation or why the stop condition is >1 instead of >0 (I mean besides "because it makes it work"). These are the kind of details that I was hoping to not have to memorize. It's a worthwhile exercise, but I think I prefer it with the +1 to avoid all the corner cases.

[@joffreybluthe7906]

Wait what?? Python can handle arbitrary large integers?? How does that work exactly? I've never heard that before... I looked on Google but could not find an explanation of how that works. I just found things like "it is possible to handle larger values as memory is available" but that's not much of an explanation...

[@ДмитроПрищепа-д3я]

Internally, at least in the reference implementation of python, it's stored as a struct with an unsigned long length and an array of digits of that length. Digit here is either an unsigned long or an unsigned short. And then there's just the classic implementation of arbitrary-length arithmetic operations, as far as I know.

[@joffreybluthe7906]

@@ДмитроПрищепа-д3я thx for the explanation! :)

[@atifadib]

perfect :)

[@mCoding]

Thanks!

[@hamoodhabibi7026]

Wait im confused when he said False value and True value shouldnt it be the reverse

[@hamoodhabibi7026]

I'm back on the grind, and now understand lol.