FAQ: Binary Search: Python - Recursive Binary Search: Review and Refactor

This community-built FAQ covers the “Recursive Binary Search: Review and Refactor” exercise from the lesson “Binary Search: Python”.

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

Search Algorithms

FAQs on the exercise Recursive Binary Search: Review and Refactor

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!

Will the use of pointers in this exercise improve the time complexity of the binary search algorithm?
If no, then what’s the point of using pointes here?

To save the space? Besides time complexity we have to think about space complexity.

def binary_search(sorted_list, left_pointer, right_pointer, target):
  # this condition indicates we've reached an empty "sub-list"
  if left_pointer >= right_pointer:
    return "value not found"
	
  # We calculate the middle index from the pointers now
  mid_idx = (left_pointer + right_pointer) // 2
  mid_val = sorted_list[mid_idx]

  if mid_val == target:
    return mid_idx
  if mid_val > target:
    # we reduce the sub-list by passing in a new right_pointer
    return binary_search(sorted_list, left_pointer, mid_idx, target)
  if mid_val < target:
    # we reduce the sub-list by passing in a new left_pointer
    return binary_search(sorted_list, mid_idx + 1, right_pointer, target)

In this code on performing a binary search with two pointers, I have a doubt on the line where we’re checking the condition, if left_pointer >= right_pointer for returning “value not found”. However, if left_pointer == right_pointer, doesn’t that mean we have one element in the list ?

I was confused by this too. Its because they call the algorithm with the right pointer being : right_pointer = len(sorted_list), which is unintuitive because if you called sorted_list[right_pointer] you would get an idex out of range error.

If they start the right_point as right_pointer=len(sorted_list) - 1 (which is an actual valid index) then you the line your questioning would be: if left_pointer > rigth_pointer:…

Hope that helps.

1 Like

Hi, I don’t understand why when mid_val > target, we reset the right pointer to mid_idx instead of mid_idx - 1.

def binary_search(sorted_list, left_pointer, right_pointer, target): # this condition indicates we've reached an empty "sub-list" if left_pointer >= right_pointer: return "value not found" # We calculate the middle index from the pointers now mid_idx = (left_pointer + right_pointer) // 2 mid_val = sorted_list[mid_idx] if mid_val == target: return mid_idx if mid_val > target: # we reduce the sub-list by passing in a new right_pointer return binary_search(sorted_list, left_pointer, mid_idx, target) if mid_val < target: # we reduce the sub-list by passing in a new left_pointer return binary_search(sorted_list, mid_idx + 1, right_pointer, target) values = [77, 80, 102, 123, 288, 300, 540] start_of_values = 0 end_of_values = len(values) result = binary_search(values, start_of_values, end_of_values, 288) print("element {0} is located at index {1}".format(288, result))