I am trying to implement Binary Search in Python with recursion.

I write code above:

space = [i for i in range(4096)]

# Recursive:
def binarySearchRec(arr, low, high, target):
    if high >= low:
        mid = (high   low) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            return binarySearchRec(arr, low, mid-1, target)
        else:
            return binarySearchRec(arr, mid, high, target)
    else:
        return -1

if __name__ == '__main__':
    element = random.choice(space)
    print(f"Index: {binarySearchRec(space, 0, len(space)-1, element)} | Number: {element}")

This should return answer in max 12 steps because O(log(N)) complexity. But some runs it exceeds max call stack. How can i prevent this i can't find why.

I will be preciate for an answer.

CodePudding user response：

Your function works, except in the case where variable 'high' is one above 'low', and the target is equal to the high variable. This is because high >= low is true, but mid rounds down to low, which is not equal to target. You could add:

if high - 1 == low:
    if arr[low] == target:
        return low
    return high

before or after the if high >= low: line. Also, you don't need to call arr[x], because arr[x] == x, so arr[x] evaluates to x and you can replace it.

CodePudding user response：

Off-by-one errors are hard to debug in problems like this one. You have two issues -

1. When target is less than arr[mid], the sub-problem is low, mid
2. When target is greater than arr[mid], the sub-problem is mid 1, high

I find it helps to write the < condition and the > condition. If neither of those conditions are met, then == is by default the else condition.

def binary_search(arr, target, low, high):
  if low >= high:
    return -1
  else:
    mid = (low   high) // 2
    if target < arr[mid]:
      return binary_search(arr, target, low, mid)       #1
    elif target > arr[mid]:
      return binary_search(arr, target, mid   1, high)  #2
    else:
      return mid                                        # target == arr[mid]

def search(sorted_arr, q):
  return binary_search(sorted_arr, q, 0, len(sorted_arr))

foo = list(range(1000000))
print(search(foo, 523407))

523407

Note for this particular problem, you do not have to expand range into a list. If you are actually searching a range, this can save a considerable amount of memory. This is because Python ranges allow you to access elements directly using [], just like lists -

bar = range(1000000)
print(search(bar, 683495)) # pass in range directly

683495