I am new in python I am implementing a binary search on the big array of values where the length of Array is 258000, I have tested my code on linear search it also crashes when it exceeded maximum recursion depth, thats why I use binary. but binary not working on that big array also, as I test my code on small array it works fine, here is a code:
A = ['John', 'William', 'James', 'Charles', 'George', 'Frank']
names = sorted(A)
print(names)
n = len(names) - 1
low = 0
high = n
key = "James"
def binarysearch(a, l, h, k):
if h < l:
return l - 1
mid = l + (h - l // 2)
if k == names[mid]:
return mid
elif key < names[mid]:
return binarysearch(a, l, mid-1, k)
else:
return binarysearch(a, mid+1, h, k)
index = binarysearch(names, low, high, key)
print("The given Name ", key, "is a Place ", index)
I know how to increase the sys.setrecursionlimit() I have tried but it still kills because it exceeded the RAMs limit, I have use bisect code of python and it works fine, But as I am new in python I want to absorb the in-depth concept of algorithm, rather than a builtin functions, if someone can help me to correct this code I will appreciate this, thanks
You don't need recursion at all. You can do binary search in iterative way. However, even with recursion you shouldn't hit maximum recursion depth with such array. The reason you are hitting this is that you are not doing binary search correctly.
mid = l + (h - l // 2)
This is obviously wrong as l // 2 will be evaluated first. What you want is:
mid = l + (h - l) // 2
Also, I don't get the rationally behind returning l - 1 when h < l. Normally you should return -1 to signal that key is not found. l - 1 at some recursive step may provide a valid index for initial call.
And finally, if the list is not sorted than there is no point to sort it first and then doing binary search, unless you do lots of searches on same array, since sorting will take more time than a simple linear search.