Assignment 1 help sought

Data Structures and Algorithms in Python Assignment 1 - Binary Search and Linked Lists Prac
#1

Anyone,kindly help me out . I have tried a million times but cannot even get the first test “test” to pass and only 2 of the other test cases in “tests”! Where may I be wrong?

def count_rotations_binary(nums):
lo = 0
hi = len(nums)-1

while lo<=hi:
    mid = (lo + hi)//2
    mid_number = nums[mid]
    
    # Uncomment the next line for logging the values and fixing errors.
    print("lo:", lo, ", hi:", hi, ", mid:", mid, ", mid_number:", mid_number)
    
    if mid >=lo  and nums[mid-1]<nums[mid]:
        # The middle position is the answer
        return mid
    
    elif nums[mid]<nums[hi]:
        # Answer lies in the right half
        #hi = mid - 1 
        lo = mid + 1
    
    else:
        # Answer lies in the left half
        lo = mid + 1
        #hi = mid - 1

return 0
#2

I don’t see you setting the hi number in the code you posted. So with what you have, if it doesn’t find the answer immediately, it’s always going to move to the right in the list.

1 Like
#3

Thanks. It was set, only that I mistakenly missed it out when copying.

def count_rotations_binary(nums):
       lo = 0
       hi = len(nums)-1

but still I can’t figure out the error. Any comment please, on the rest of the code?

#4

Hi,

I’ve spotted one mistake: check your elif and else conditions, in both you’re using lo = mid + 1

Good luck!

1 Like
#5

yes he seems to be confused with left half and right half both are reversed.

Check if the middle element is smaller than the last element in the list if yes then the answer lies in the left half of the list if not then vice-versa

elif nums[mid] < nums[hi]:
# Answer lies in the left half
hi = mid - 1

else:
# Answer lies in the right half
lo = mid + 1

1 Like
#6

You initialized hi with those statements, but you never set hi during the loop, so it always moves to the right. Let’s look at the algorithm stated in plain English.

We are given a rotated sorted list, The index position of the smallest number in the list is the minimum number of rotations needed to produce that list. So we want to use binary search to find that number.

  1. Starting with the entire list, we set our start position to the start of the list example: lo = 0 and the end position to the length of the list - one example: hi = len(list) - 1
  2. We then take the position in the middle of the list to get the value mid = (lo _ hi) // 2
  3. We then start a loop with the condition that while our starting position is less than or equal to the end position, we will execute the loop.
  4. We look at the value in the middle, if that value is less than the previous value, we have the answer. and we return the middle position mid
  5. Otherwise, if the middle value is less than the ending value, then then answer is in a position to the left, which means it is between the start and middle position. We then set our ending position hi to mid - 1 and repeat the process
  6. If the previous two conditions were false (which means our middle value is greater than the ending value), then the answer is to the right. This means that the answer is between the middle and ending positions, so we set our start position lo to mid + 1 and repeat the process

Finally, if we don’t find an answer with our loop, this means that the list was already sorted and we return 0

I hope this helps you sort out the code that you have written.

1 Like
#7

Lots of thanks sir, you have made it for me. You cant believe the number of times I had taken!. Thanks again for the comprehensive effort.
God bless