Given a list of distinct integers (decreasing order), return True if there is atleast position p, such that the value at position p is p. For instance, List = [4, 3, 2, 0], the function returns true since 2 is at index 2.
I know we can just go for a loop and check if list[i] == i.
I was wondering if and how this can be implemented with the divide and conquer algorithm?
My base cases are:
- L is empty, return False.
- If L[0] is negative, return False. Since list is in decreasing order, all values will be negative, and all index are positive. SO we will not get a match. For simplicity, i am just considering positive index.
I am a bit confused how to divide the list here. Since splitting the list in 2, each list would have index [0:n/2]. So comparing the the values and index dont make sense.
Appreciate some help!
Advertisement
Answer
You only need to compare the starting and ending values of a list to the values in the list index to see if it’s possible.
Code
def divide_conqueer(lst, indexes = None): if indexes is None: indexes = list(range(len(lst))) # create list index if not lst: return False elif len(lst) == 1: return lst[0] == indexes[0] elif lst[0] < indexes[0] or lst[-1] > indexes[-1]: # Compare values of beginning and end of the list to the # list indexes of the beginnning and end # There is a matching value to index only if beginning value >= starting index and # ending value <= ending index return False else: # Divide values and intervals in half and test each half return (divide_conqueer(lst[:len(lst)//2], indexes[:len(indexes)//2]) or divide_conqueer(lst[len(lst)//2:], indexes[len(indexes)//2:]))
Test
print(divide_conqueer([4, 3, 2, 1])) # Output: True