For exercising reasons, I am trying to implement a class SSM
which stands for Static Sorted Map in python in order to implement the methods
min_value(self)
: find the minimum value
max_value(self)
: find the maximum value
search(self, key)
: to find an element in the list
The list is assumed to be sorted.
Here is the code for the class:
class SSM: def __init__(self, A): self.sorted_list = A[:] #the list, assume A is sorted def min_value(self): return self.sorted_list[0] def max_value(self): return self.sorted_list[-1] def search(self, K): def __Bin_Search(s, e, K): # local function # implementation pseudocode if s == e: if self.sorted_list[s] == K: return True, s # return True and position else: return False x = math.ceil((s+e)/2) if self.sorted_map[x] == K: return True, x # return True and position if self.sorted_list[x] > K: return __Bin_Search(s, x-1, K) # go recursive else: return __Bin_Search(x+1, e, K) # go recursive return __Bin_Search(0, len(self.sorted_list), K) # call __Bin_Search
As you can see from the code, for the method search (self, K)
I have an inner function __Bin_Search(s, e, K)
which goes recursive on the left or right of the list in order to find the element (it is based on the Binary Search Algorithm).
And so, I expect that the methods search (self, K)
returns the result given by __Bin_Search
since it is called in the last line.
My problem is that by using search(self, K)
nothing is returned.
A = [45, 33, 36, 30, 27, 40, 16, 27] A.sort() ssm = SSM(A) ssm.search(33)
Where is the error in the code? How can I fix that?
Advertisement
Answer
Your list always has a length greater than 0
so s will never equal e and therefore never reach a return statement. You need to add a conditional statement in __Bin_Search
where s != e
.