Computer scienceAlgorithms and Data StructuresAlgorithmsPrinciples and techniques

Divide and conquer

Theory

Input and output

Report a typo

Wow! This problem is kind of tricky. If you're ready to put your thinking cap on, brace yourself, and good luck! Otherwise, you can skip it for now and return any time later.

Below you see a function implemented according to the divide and conquer paradigm.

function f(array, left, right, value):
    if left >= right then:
        return 0
    else: 
        if left == right-1 then:
            if array[left] == value then:
                return 1
            else:
                return 0
        else:
            middle = (left + right) div 2
            return f(array, left, middle, value)
                   + f(array, middle, right, value)

Here div means integer division, and we are using zero-based indexing. Please note that the function processes the array from the left index to the right index but does not include the right index.

What statements below correspond to the correct output of the function?

Select one or more options from the list
___

Create a free account to access the full topic