1

I'm trying to write a binary search algorithm using recursive programming in python. My test array is [1, 5, 8, 10, 14, 20]. If a number is in the array, the program is supposed to return 1, otherwise it will return 0. If the number for test is 1, it will first get the middle element with the index floor(len(array)/2), which is 10 in this test case and and compare it to 1. It will recursively do the same procdure for the subarray [1, 5, 8, 10] until there are only two elements in the subarray, that is [1, 5]. Then it compares the test number 1 with each of them. The program is supposed to return 1 if the test number is contained in the final subarray of two elements and 0 otherwise. However, surprisingly, the final result is None.

I guess that the reason for this might be the recursion is not terminated. How can I fix this problem?

import numpy as np
import math

def myBinarySearch(array, x):  # array is sorted
    print("length of array: " + str(len(array)))
    if (len(array)==2):
        # print("length of array: " + str(len(array)))
        # print("OK")
        print("array" + str(array) + "\t" + str(array[0]) + " " + str(array[1]) + "\telement: " + str(x))
        if (x==array[0]):  # element is found
            print("find: 0")
            return 1
        elif (x==array[1]):
            print("find: 1")
            return 1
        else:
            print("not find")
            return 0
    midIdx = math.floor(len(array)/2)
    print("mid element: " + str(array[midIdx]))
    if (x==array[midIdx]):  # element is found
        return 1  
    if (x<array[midIdx]):
        myBinarySearch(array[0:midIdx+1], x)
    if (x>array[midIdx]):
        myBinarySearch(array[midIdx, len(array)], x)
        
    
A = np.array([1, 5, 8, 10, 14, 20])
# B = np.array([1, 3, 5, 7, 9, 11, 20, 14, 16])
# B = np.array([1, 21, 20, 14])
B = np.array([1])
C = np.zeros(shape=(1,len(B)))
for i in range(len(B)):
    #print("B[i]: " + str(B[i]))
    inArray = myBinarySearch(A, B[i])
    print(inArray, end="")
    C[0][i] = inArray
# print("\n" + str(A))
Dion Saputra
  • 322
  • 2
  • 15
Wenjie Yu
  • 47
  • 4

1 Answers1

2

When you recurse down e.g. at myBinarySearch(array[0:midIdx+1], x), you are not returning the result.

E.g.

if (x<array[midIdx]):
    myBinarySearch(array[0:midIdx+1], x)
if (x>array[midIdx]):
    myBinarySearch(array[midIdx, len(array)], x)

Should be

if (x<array[midIdx]):
    return myBinarySearch(array[0:midIdx+1], x)
if (x>array[midIdx]):
    return myBinarySearch(array[midIdx, len(array)], x)
Tom Dalton
  • 6,122
  • 24
  • 35