Binary Search in Python: Find Closest Number

[@Cloud-577]

Thank you! This was very helpful. I'm self taught student so content like this is like a goldmine

[@LucidProgramming]

Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon!

[@alexandraxu4007]

awesome explanation, you made it so clear each step, love your programming videos. Just one thing, the code doesn't work when there are two elements in the array. I just added another edge case, then it worked fine. if len(array) == 2: if abs(array[0]-target)> abs(array[1]-target): return array[1] else: return array[0]

[@LucidProgramming]

Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon! Also, thanks for pointing that out. Feel free to make a PR in the code on GitHub. Thanks again!

[@samarthbhandari1360]

Hi great work on the videos, I have been following your videos for a few days now. I just wanted to point out one thing, when you calculate the midpoint it is better to calculate it as mid = low + (high-low)//2. This would prevent overflowing in case of extremely large inputs since if our low + high exceeds the maximum integer value it will calculate the midpoint wrong and is a very basic mistake a lot of people tend to overlook, especially from an interview perspective. Thanks for all these videos, please keep adding to these!

[@LucidProgramming]

Hi Samarth. First off, thank you so much for your comment. It's always a real treat to know that these videos serve some utility, and I'm happy to hear they have been useful to you. Regarding your comment on the calculation of the midpoint, this would only apply if you were coming in something like C where integer overflow is an issue. Python will cast automatically if it goes beyond the integer limits, so this step in Python is completely unnecessary. Hope that makes sense. Cheers!

[@captain_vegan]

Local variable 'min_diff_left' might be referenced before assignment

[@maximpodkolzin865]

either I'm doing something wrong or algorithm does not work for case when target number is not in the array and it's smaller than array's minimum, e.g [1,2,3,4,5,6], target = -1

[@LucidProgramming]

Are you using the code that is present on the GitHub page?

[@namefunction]

This playlist is very helpful. Well explained and intriguing solution.

[@LucidProgramming]

Thank you, Cytla! I'm glad that the playlist is helpful for you. Cheers, and thanks again for watching and for your comment!

[@KK-9-KK]

This is a great video. Really appreciate it. #Just one question: if use array = [1, 2, 3, 4, 11, 14, 16, 17, 20] as an example and target value is 10, then mid is 11 and is closest to 10, but it will be skipped using your code, right? probably we need to include a line to compare A[mid]-target with the mid_diff_left and mid_diff_right.

[@LucidProgramming]

Hi Kun, thanks for your comment! Hmm, have you tried running the code on the example provided? I believe it behaves properly with the input you provided unless I'm missing something. Let me know if so. Thanks!

[@KK-9-KK]

@@LucidProgramming Sure, will give it a try. I mean, logically the code is going to skip A[mid] if A[mid] is the closest number, because the only situation that is going to return A[mid] by the code is when A[mid] is equal to target. The code is mainly focusing on comparing the magnitude of A[mid-1]-target and that of A[mid+1]-target and figure which half section to move to for further comparison. In the comparison which is key of the code, A[mid] is not considered if I understand the logic correctly. Anyway, I have been following the binary search series of your video and find them really helpful to beginners like me. Thanks a lot.

[@LucidProgramming]

@@KK-9-KK Hi Kun. Thanks for breaking that down logically here in the comment. Good to see it all on paper. Also, really happy to know that the binary search videos have been helpful to you. Thanks again for your comment, and have a great day!

[@LucidProgramming]

@@KK-9-KK Hi Kun. Thanks for writing the logic down in comment form. Good to see it all on paper and written out. Also, thanks for your comment on the binary search series. I'm really thrilled to know that those videos have been useful to you. Cheers, and thanks again for watching!

[@gautamjain6122]

I had the exact same doubt

[@sudarshanhavale972]

Your videos are very helpful to learn algorithms, keep it coming :) Here is another version of the solution in which I tried to handle "get minimum difference value" differently (which works fine I guess), but I would appreciate it if you could review my code, and let me know whether it's worth skipping that "left and right difference" logic. ``` def find_closest_number_2(input_list, target): min_diff = float('inf') low = 0 high = len(input_list) - 1 closest_num = None # Edge cases to handle empty lists # and lists with single element. if len(input_list) == 0: return None if len(input_list) == 1: return input_list[0] while low target: high = mid - 1 else: return input_list[mid] return closest_num A = [1, 2, 4, 5, 6, 6, 8, 9] B = [2, 5, 6, 7, 8, 8, 9] print (find_closest_number_2(A, 11)) # Result 9 print (find_closest_number_2(B, 4)) # Result 5 ```

[@LucidProgramming]

Thank you, and thanks for sharing! :)

[@williamkwon7951]

could you explain what is the min_diff part? I am not sure why set that if min_diff_left < min diff because this will be always true since there is no number bigger than infinity. I am not sure what you try to check in this statement? is there case this condition is not true?

[@LucidProgramming]

But we're checking if it's smaller than inf, not bigger.

[@williamkwon7951]

@@LucidProgramming sorry I meant smaller than inf, this will be always true so what is the point of checking it?

[@LucidProgramming]

@@williamkwon7951 Because what other value would it make sense to start at but a value that is the largest possible value?

[@asiradnan4434]

I tried your code and found from the array [1,2,6,7,8,9], if the target is 0, it gives 2 as output whereas it should be 1, right?

[@DoxxingWhoami01]

Thanks for doing this exercise, I liked it, and if it continues like this

[@LucidProgramming]

Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon!

[@elisad8372]

Hi, super helpful video! Question - I tried with this test case "a7 = [0,3] print(find_closest_num(a7, 1))" but got an error "UnboundLocalError: local variable 'min_diff_left' referenced before assignment". So I think it's because the `if mid > 0' condition is skipped (since mid = 0), so 'mid_diff_left' is never assigned. How can we fix it in this case? I'm thinking adding an 'else' statement somewhere but not sure how to... thank you!

[@LucidProgramming]

You could add an `else` statement, or, you could also initialize the `min_diff_left` and `min_diff_right` variables to something like `None` or `float("inf")` and `float("-inf")` depending on what your requirements/preferences are. Hope that helps, and thanks again for the question. Cheers.

[@idan4329]

Are you checking A[mid+1] and A[mid-1] due to the division by two? (even number of elements)

[@LucidProgramming]

No. This has to do with where the new bounds of the array are placed. You can see in the video that we do this approach on both an array of even and odd size.

[@adrift4315]

in this code, if we input the array [1,-2,-8,4,5], the output is -2. if i print the mid, it is 2 and 3. why are there 2 values of mid? and if i debug this, it shows 2 as mid but works with mid as 3!!

[@LucidProgramming]

"in this code, if we input the array [1,-2,-8,4,5], the output is -2." -- This doesn't make sense, what is your target here?

[@adrift4315]

@@LucidProgramming sorry damn lol. The target is 0

[@rajeshmanghani5349]

I think if you checked with the last item, you would have saved lot of time for eg. if target > A[len(A)-1]: return A[len(A)-1]

[@LucidProgramming]

Hi Rajesh. I think this will fail in most cases, right? Are you proposing this line as a replacement for some line or as the whole solution?

[@anshulvairagade1604]

Sir, I didn't understand those if statements If mid + 1 < Len(A): And min > 0 Please help me !

[@LucidProgramming]

What don't you understand about it?

[@anshulvairagade1604]

@@LucidProgramming I just got confused, why and how those if statements works

[@LucidProgramming]

@@anshulvairagade1604 I don't know where I should direct your level of confusion though. Do you not understand what a variable is? Are you struggling with what an "if" statement is? etc. I don't know how to help without more context.

[@anshulvairagade1604]

@@LucidProgramming I m not getting how we ensure our of bound using those if statement Mid + 1 > 0 or Min > 0 Sorry if you didn't getting it, But thanks a lot,you tried helping me Your tutorials are awesome , the best programming channel for DS and algorithms on KZbin Cheers!

[@anshulvairagade1604]

@sniper 3point thanks man.

[@sanjaya8397]

sorry just a silly question if array = [2,4,6,8,10] and target value is 5 than abs(4-5)=1 and 6-5=1 does this program is intended to show only right value as in my case it always shows 6 as output.

[@sanjaya8397]

sorry the question was really silly my typo mistake

[@LucidProgramming]

No problem, so you resolved it?

[@dylanl2444]

I like watching your videos. For this question, why not just compare abs(A[mid] - target) with min_diff like below? import sys def find_closest_num(A, target): min_diff = sys.maxsize low = 0 high = len(A) - 1 closest_num = None if len(A) == 0: return None if len(A) == 1: return A[0] while(low target: high = mid - 1 else: return A[mid] return closest_num

[@LucidProgramming]

Hi Dylan. Thanks, glad you enjoy the videos. Are you just asking why use float('inf') instead of sys.maxsize?

[@dylanl2444]

@@LucidProgramming No, I mean replace this part if mid + 1 < len(A): min_diff_right = abs(A[mid+1] - target) if mid > 0: min_diff_left = abs(A[mid-1] - target) if min_diff_left < min_diff: min_diff = min_diff_left closest_num = A[mid-1] if min_diff_right < min_diff: min_diff = min_diff_right closest_num = A[mid+1] with if abs(A[mid] - target) < min_diff: min_diff = abs(A[mid] - target) closest_num = A[mid] I have run through a bunch of tests and got correct results with it

[@LucidProgramming]

@@dylanl2444 Ah gotcha. Hmm, I don't see any reason this shouldn't work. You might want to make sure that your test cases work on the edge cases. Such as an empty list, a list with a small number of elements, etc. etc. From a quick glance though, it does look like it should work. Sorry for my initial misunderstanding!

[@tobyconoley5511]

does this work for different sizes of lists that have odd or even amounts of values inside?

[@LucidProgramming]

This is something that would be easier to verify rather than asking, don't you think?

[@tobyconoley5511]

@@LucidProgramming I'm studying the video now

[@LucidProgramming]

@@tobyconoley5511 Cool. Sounds like something that you could answer from your studying then I take it, right?

[@tobyconoley5511]

@@LucidProgramming yeah thanks. Also is the only way to do this with binary search trees to put the elements into an array?

[@LucidProgramming]

@@tobyconoley5511 This video has nothing to do with binary search trees.

[@tom.24fps34]

If i try out this program, it'll say I cant subtract lists. How do I fix this problem?

[@LucidProgramming]

What does it say exactly? Are you sure you're running the code as I have it on my Github? I have no such error.

[@vnpikachu4627]

Great works as always this lesson helped me solve two problem i had struggled recently. Could this method be applied to problem '' find subsequence of a sorted array has sum closest to a given value''?

[@LucidProgramming]

Hi Hữu. Thanks for the comment and question :). I don't believe this method would be applicable to the case you described (at least, I currently don't see a way that it can be helpful). I did do a bit of searching and found some articles on GeeksforGeeks that had a pretty similar variant problem to the one you described. In looking at their solutions, however, it seems they are making use of other techniques that don't necessarily make use of binary search. Hope that is helpful. Cheers, and thanks again for watching! :)

[@GopalaKrishnangk21894]

How about using iterative approach here? def closes_number(l1, target): diff = None closest_no = None for data in l1: if target > data: temp = target-data elif target < data: temp = data - target else: return data if diff is None: diff = temp elif temp < diff: diff = temp closest_no = data return closest_no

[@LucidProgramming]

Sure, there's no reason you couldn't use that over the recursive approach. Cheers, and thanks for sharing!

[@tecnorea]

Does not work, when the target number is Zero.

[@LucidProgramming]

Yes it does. I just tested it.

[@dinokrivic5486]

This code works only if array is small?Cause if i add more numbers its not working properly.Can someone help?

[@LucidProgramming]

What do you mean by "small"? Are you sure your code matches mine on the GitHub link in the description?

[@dinokrivic5486]

@@LucidProgramming i tought that my code isnt the same then i copied your code and relaized the problem is when target is 0 and list is big and containes large numbers

[@LucidProgramming]

@@dinokrivic5486 It's not clear from your comment whether you were able to fix this or not.

[@dinokrivic5486]

@@LucidProgramming i had training so i couldnt even try. I'll try now the problem is when i set target to 0 and the list containes big number it skips first closest number and give me second. Can you pls also try to fix it?

[@LucidProgramming]

@@dinokrivic5486 You need to give more explicit examples. I don't know what you mean, and I'm not convinced there is anything here that needs fixing.

[@subhan5092]

It shouldve been in c++ but atleast I understood it

[@LucidProgramming]

Why should it have been in C++?

[@dinokrivic5486]

I found another error.If array contains only 2 numbers you will get this error: Traceback (most recent call last): File "main.py", line 117, in y = find_closest_num(A, 4) File "main.py", line 96, in find_closest_num if min_diff_left < min_diff: UnboundLocalError: local variable 'min_diff_left' referenced before assignment

[@LucidProgramming]

Yep, those are edge cases that need some code to cover. If you want to make a pull request, by all means, please do so and I will update the code on GitHub.

[@dinokrivic5486]

@@LucidProgramming I'm just begginer i don't know what that pull request even mean still thank you for your really quick responses.It would be good if you could update that code.

[@LucidProgramming]

@@dinokrivic5486 For a GitHub repo, if you want to make changes to it, you can put up your code changes in what's called a pull request. This allows others to contribute to software projects and such.

[@adirbarak5256]

it does not work because even if the list is sorted you can have a case of identical repetition in both sides like - [0,1,2,2,2,2,2,2,2,2,8,10] find closest to 6 so use set(data) on your data list before doing anything (right in the begining of the function) dataset = list(set(dataset))).sort()

[@LucidProgramming]

I don't understand your comment. The code I have works on the example you provided.

[@adirbarak5256]

@@LucidProgramming it wont work because you use 2 if statements one after the other, in this case the latter one will override and decide the direction to go from that point onwards (sometimes you will default to the wrong left side and sometime the to wrong right side)

[@LucidProgramming]

@@adirbarak5256 The two if statements in sequence will not make a difference for your point as the condition we are checking will not change between them. Again, I'm not able to replicate your issues, I would check your code against my code on GitHub.

[@adirbarak5256]

@@LucidProgramming for example: your first if statement decides if we ignore the right half, the second if statement decides if we ignore the left half. the latter one will override the first in a case of identical comparisons (n on both sides of middle)

[@LucidProgramming]

@@adirbarak5256 I'm still not seeing how the structure of my code prevents you from getting the correct answer.

[@ebrahimmohammadsaleh1427]

# this i write answer is same A = [2, 5, 6, 7, 8, 8, 9] def find(arr, val): s=[] fi=[] mid=len(A)//2 if val=A[mid]: for i in range(len(A[mid:])): dif=abs(A[i]-val) s.append(dif) else: s.append(A[0]) return m=min(s) for i in range(len(s)): if s[len(s)-1-i]==m: fi.append(A[len(s)-1-i]) print(fi[0]) find(A, 4) # ans is 5

[@slmasuud9149]

Byo, this man talk the whole video!!👎

[@kalyandeshpande2173]

You are not convenincing

[@LucidProgramming]

Hi Kalyan. Do you mean "convincing"? If so, why no? What could I improve to make sure future videos are better for you? I would appreciate your feedback. Cheers, and thanks for watching!

[@kalyandeshpande2173]

Sir,I did not intent to heart you,but you explained it very fast,which is sounding bit complicated

[@LucidProgramming]

Hi Kalyan. No problem, I want to know if I can improve my content on this channel. I would recommend that if the video is too fast, you could try slowing down the playback speed. Hopefully that helps a bit. Thanks again for your comment, I'll try to keep that in mind when I make future videos. Cheers!

[@gusmarx1550]

@@LucidProgramming I thought this was a good video / speed. I just assume anyone watching this knows about python and basic binary search already. Also, thank you. This will help me on my homework

[@LucidProgramming]

@@gusmarx1550 Hi Gus. Thanks, I appreciate that. I think it's better to err on the side of assuming that these things are not known. That way, those who do know them can skip, and those that don't can benefit. Cheers!