Binary Search Base Case

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 need clarification on this.

Best bet with recursion is to plot it out or to have some really nice formatted strings while you’re still getting used to it. I say that because it’s often the best debugging tool for recursion as well. You can also use things like Python Tutor - Visualize Python, Java, JavaScript, C, C++, Ruby code execution to see how it’s being executed, which is sometimes useful.

I say this regardless of whether an instruction set is correct or incorrect, as a programmer has to overcome flaws in instructions in either case :slight_smile:

1 Like

Thank you so much for your kind help ! This visualization tool is everything I needed at the moment.

This topic was automatically closed 41 days after the last reply. New replies are no longer allowed.