-1
def binary_search(input_array, value):
right_search=[]
left_search=[]
"""Your code goes here."""
if len(input_array)%2==0:
    mid_ind=(len(input_array)/2)-1
else:
    mid_ind=int(len(input_array)/2)

if input_array[mid_ind]==value:
    return mid_ind
elif input_array[mid_ind]<value:
    for ri in range(mid_ind+1,len(input_array)):
        right_search.append(input_array[ri])
    if right_search==[]:
        return -1    
    
    binary_search(right_search,value)
elif input_array[mid_ind]>value:
    for li in range(0,mid_ind):
        left_search.append(input_array[li])
    if left_search==[]:
        return -1
    
    binary_search(left_search,value)

test_list = [1,3,9,11,15,19,29]
test_val1 = 25
test_val2 = 15
print (binary_search(test_list, test_val1))
print (binary_search(test_list, test_val2))

it prints out none for both the test cases.i have used recursion for every sub array in main array.so that if mid element not matches the value to be found.It creates a left or right sub array according to value and then using recursion

Karl Knechtel
  • 62,466
  • 11
  • 102
  • 153
Darshan walunj
  • 3
  • 3
  • Please read about [How to debug small programs](http://ericlippert.com/2014/03/05/how-to-debug-small-programs/). You can also use [Python-Tutor](http://www.pythontutor.com/visualize.html#mode=edit) which helps to visualize the execution of the code step-by-step. – Tomerikoo Apr 13 '21 at 20:22
  • 1
    You are not returning a value for the none-base-cases (e.g. you only ever `return -1`) – MegaIng Apr 13 '21 at 20:22
  • 2
    Does this answer your question? [Recursive function returning none in Python](https://stackoverflow.com/questions/19215141/recursive-function-returning-none-in-python) – Tomerikoo Apr 13 '21 at 20:22

1 Answers1

1

Assuming a return value of -1, means the element being searched for is not present in the list, and 0, means the element is present, the reason the binary_search function is returning None, is because when recursion occurs, the return value of the function is not being returned to its caller, therefore when the recursion loop finishes, it has nothing to return.

The fix to this problem would be to add the return keyword before the recursive calls:

def binary_search(input_array, value):
    right_search=[]
    left_search=[]
    """Your code goes here."""
    if len(input_array)%2==0:
        mid_ind=(len(input_array)/2)-1
    else:
        mid_ind=int(len(input_array)/2)

    if input_array[mid_ind]==value:
        return mid_ind
    elif input_array[mid_ind]<value:
        for ri in range(mid_ind+1,len(input_array)):
            right_search.append(input_array[ri])
        if right_search==[]:
            return -1    
        
        return binary_search(right_search,value)

    elif input_array[mid_ind]>value:
        for li in range(0,mid_ind):
            left_search.append(input_array[li])
        if left_search==[]:
            return -1
        
        return binary_search(left_search,value)

test_list = [1,3,9,11,15,19,29]
test_val1 = 25
test_val2 = 15
print (binary_search(test_list, test_val1))
print (binary_search(test_list, test_val2))
JojoTheCodeDude
  • 110
  • 10