FAQ: Technical Interview Problems in Python: Lists - Rotation Point: Binary Search

This community-built FAQ covers the “Rotation Point: Binary Search” exercise from the lesson “Technical Interview Problems in Python: Lists”.

Paths and Courses
This exercise can be found in the following Codecademy content:

Technical Interview Practice: Python

FAQs on the exercise Rotation Point: Binary Search

There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply (reply) below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply (reply) below!

Agree with a comment or answer? Like (like) to up-vote the contribution!

Need broader help or resources? Head here.

Looking for motivation to keep learning? Join our wider discussions.

Learn more about how to use this guide.

Found a bug? Report it!

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

I got answer right, but the run button keeps spinning and Next button keeps gray

Notably, the solution provided by the problem generally works, but it won’t properly return the result in cases where lists have repeating values. For example, if the rotation_list is something like [2,2,2,3].

1 Like

I did get a workable solution, but it was quite complicated to account for the scenario where the list could be in either normal or reversed order. My code is below, but would love to know how it could be simplified. Also the test samples on the page left out a number of cases, and while the suggested solution will work for the given test cases, it won’t work for many cases (hence some of my additional code).

# find rotation point 
# O(logN) time requirement
# return index of "rotation point" element

def rotation_point(rotated_list):
  low_idx= 0
  high_idx = len(rotated_list) - 1
  #check characteristics of list
  mid = int((low_idx + high_idx) / 2)
  if (rotated_list[0] < rotated_list[mid] and rotated_list[mid] < rotated_list[len(rotated_list) - 1]):
    print("list is already sorted left to right")
    return 0
  if (rotated_list[0] > rotated_list[mid] and rotated_list[mid] > rotated_list[len(rotated_list) - 1]):
    print("list is already sorted right to left")
    return len(rotated_list) - 1
  if rotated_list[0] > rotated_list[len(rotated_list) - 1]:
    print("sorted forward")
    sort_order = "fwd"
  else:
    print("sorted backward")
    sort_order = "bkwd"

  while low_idx <= high_idx:
    mid = int((low_idx + high_idx) / 2)
    print(f"mid is {mid}")
    mid_next = (mid + 1) % len(rotated_list)
    mid_prev = (mid - 1)
    if rotated_list[mid_prev] > rotated_list[mid] and rotated_list[mid_next] > rotated_list[mid]:
        return mid
    if sort_order == "fwd":
        print("sorting_forward")
        if rotated_list[mid] < rotated_list[high_idx] and rotated_list[mid] < rotated_list[mid_next]:
            high_idx = mid - 1
            print(f"new high_idx is {high_idx}, low_idx is {low_idx}")
        else:
            low_idx = mid + 1
            print(f"new low_idx is {low_idx}, high_idx is {high_idx}")
    else:
        print("sorting_backward")
        print(f"current values are mid = {rotated_list[mid]} and mid_prev = {rotated_list[mid_prev]} mid_next = {rotated_list[mid_next]}")
        if rotated_list[mid] > rotated_list[low_idx] and rotated_list[mid] > rotated_list[mid_prev]:
            high_idx = mid - 1
            
            print(f"new high_idx is {high_idx}, low_idx is {low_idx}")
        else:
            low_idx = mid + 1
            print(f"new low_idx is {low_idx}, high_idx is {high_idx}")
  return mid
    
  
#### TESTS SHOULD ALL BE TRUE ####
print("{0}\n should equal \n{1}\n {2}\n".format(rotation_point(['a', 'b', 'c', 'd', 'e', 'f']), 0, rotation_point(['a', 'b', 'c', 'd', 'e', 'f']) == 0))

print("{0}\n should equal \n{1}\n {2}\n".format(rotation_point(['f', 'e', 'd', 'c', 'b', 'a']), 5, rotation_point(['f', 'e', 'd', 'c', 'b', 'a']) == 5))

print("{0}\n should equal \n{1}\n {2}\n".format(rotation_point(['c', 'd', 'e', 'f', 'a']), 4, rotation_point(['c', 'd', 'e', 'f', 'a']) == 4))

print("{0}\n should equal \n{1}\n {2}\n".format(rotation_point(['d', 'c', 'b', 'a', 'f']), 3, rotation_point(['d', 'c', 'b', 'a', 'f']) == 3))

print("{0}\n should equal \n{1}\n {2}\n".format(rotation_point([13, 14, 15, 16, 17, 18, 8, 9, 10, 11, 12]), 6, rotation_point([13, 14, 15, 16, 17, 18, 8, 9, 10, 11, 12]) == 6))

print("{0}\n should equal \n{1}\n {2}\n".format(rotation_point([13, 12, 11, 10, 9, 8, 20, 19, 18, 17, 16, 15, 14]), 5, rotation_point([13, 12, 11, 10, 9, 8, 20, 19, 18, 17, 16, 15, 14]) == 5))

print(rotation_point([2,1,6,5,4,3]))

print(rotation_point([6,1,2,3,4,5]))