Optional Bonus Questions Discussion - Assignment 1

Discuss the bonus optional questions from Assignment 1 here.

Use this starter template, if you’d like to create a new notebook for the bonus questions and share your solution: https://jovian.ai/aakashns/python-problem-solving-template

1 Like

Hi @aakashns, I was wondering that when we are using the predefined binary search function, inside the condition function, how do we access the nums[hi] element to compare with the nums[mid] element. The condition function receives only the mid position value as an argument and therefore it is giving the error as hi not defined as obvious. Without hi, how can we access the last element of the range and further proceed onto breaking the list in halves?

2 Likes

Hi @2019ucs0097,

I also faced the same problem. What I did to solve this is to define the lo and hi variables within the condition(nums) itself. It worked after that. Let me know your thoughts.

def count_rotations_generic(nums):
def condition(mid):
lo = 0
hi = len(nums)-1

Another way of doing it is defining the function binary_search() yourself and switching result = condition(mid) for result = condition(mid, hi, lo).

I think it only work for some cases. Because, len(nums) will be const for every iteration

Not working. just tried

Don’t forget to add both hi and lo as parameters in the condition funtion too.
Also, I made slight changes to binary_search to fit the way I solved the problem.

1 Like

Yes @ravitejadumpala888 is right. Thank you taking out the time for answering to my question. But in your solution hi will always be equal to the last element of the array/list. What we need is the last element of the part we are taking into account. Like in the case of 8 9 1 2 3 4 5 6 7, first we will check 3 and 7, then it will go on the left side 8 9 1 2. Only one argument mid with the value of index 1 will be passed to condition and we need the value 2 with index 3 but your solution will return value 7 with index 8 again.

Thank you for answering. Your solution is should work out well. Can I know what should I read up about to learn about changing generic predefined functions in pythons?

All you need is to copy the function that the Jupyter command gives you when you type ??binary_search and paste it in a new cell.
I believe Aakash has provided a Markdown cell above it to explain how ?? works somewhere in the assigment notebook.
From there you just make the changes you need.

Hi, did anyone figure out how to solve the bonus question of handling repeated numbers? For example, given a list [3, 3, 0, 0, 3, 3, 3, 3, 3, 3, 3, 3], the output should be 2. I couldn’t figure out the modification to the original function.

For the first bonus question (using Generic Binary Search Algorithm), I did not use pointer “lo” and “hi” for the condition function. What I have done is comparing nums[mid] and nums[0]. Since the numbers are not repeated, as long as nums[mid] < nums[0], I can prove that the next search is in the left half of the list. I haven’t found out any error by using this method so far (for unrepeated list).

Yes, you are right even me did not face any problem so that I have to add hi, lo while defining condition function.
@2019ucs0097 @jcawesome @tiagomiguelrs

I would recommend to recheck the condition function and how it should be defined in Lesson 1.

1 Like

Have you tested for all the cases using evaluate_test_cases()? Assuming you are searching for the smallest number in the list, your method will fail for the case of an unrotated list.

Example:
nums = [1, 3, 4, 5, 7, 8, 9], so nums[mid] == 5 and nums[0] == 1
Since nums[mid] < nums[0] is False, according to your method the next search is not in the left side of the list, thus it must be on the right side. But we can clearly see that the smallest number, ‘1’, is on the left side of the list, so your method will never find it.

1 Like

I have tested all the cases. For the example you pointed out, since the function will not return a position as long as nums[mid] is not smaller than nums[mid-1], in the end when lo>hi, the function will just return 0 or -1 for unrotated list.

Actually you’re right, your method is correct if unrotated list is supposed to output -1 (at least in my function implementation). I modified your condition such that if nums[mid] < nums[last_index], then I search the left half next (where last_index = len(nums) - 1). With this change I was able to pass all the tests and get output 0 for unrotated list. Thanks for your comment.

So for the case of empty set. Shouldn’t the return value be 0? or did i miss something in the code?

The empty list is the only test case where the generic code doesn’t work for me.

I believe the function should return 0 as that is the minimum number of rotations required to return itself. Instead, the generic binary search function returns -1. The condition function is never called, so I can’t override this.

1 Like

Hooray :grin:

3 Likes

Can anyone tell me the command used to view the source code of binary_search in jupyter.