Divide and Conquer to check if a value in a list is equal to its index-CodePudding

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!

CodePudding user response：

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