0

I'm having some trouble figuring out why my code is not working, and would appreciate if someone could point out what I'm missing. It's a basic algorithm problem: given a set of distinct sorted integers, determine whether there is an element such that a[i] = i (a[3] = 3, for example).

I've tried to debug it using print statements, but it's only making one call to FindIndex and not recursing.

Here's the code:

import math

def FindIndex(SetToSearch, beginningIndex, endingIndex):
    """Searches a list of sorted integers to see if there is some a[i] == i

    Keyword Arguments:
    SetToSearch -- a list of disctinct sorted integers 
    beginningIndex -- start point of index to search
    endingIndex -- end point to search """
    # calculate midpoint of set
    midpointIndex = math.ceil((beginningIndex + endingIndex) / 2)
    midpoint = SetToSearch[int(midpointIndex)]
    print "beginningIndex: %s, endingIndex: %s" %(beginningIndex,endingIndex)
    print "midpointIndex: %s, midpoint: %s" % (midpointIndex, midpoint)
    # check whether ending index is greater then beginning index
    if (endingIndex > beginningIndex):
        return "There is no value in this set such that a[i] = i"
    if (endingIndex == beginningIndex):
        if SetToSearch[beginningIndex] == SetToSearch[endingIndex]:
            return "a[%s] is equal to %s" % [beginningIndex, beginningIndex]
    if (midpoint == midpointIndex):
        return "The value at index %d" % midpointIndex
    if (midpoint > midpointIndex):
        print "midpoint > midpointIndex evaluated to true and executed this"
        return FindIndex(SetToSearch, 0, midpointIndex)
    if (midpoint < midpointIndex):
        print "midpoint < midpointIndex evaluated to true and executed this"
        return FindIndex(SetToSearch, midpointIndex + 1, len(SetToSearch) -1)
    else:
        "Something is wrong with your program, because you should never see this!"

sampleSet = [-10, -8, -6, -5, -3, 1, 2, 3, 4, 9 ]
lastIndex = len(sampleSet) - 1

FindIndex(sampleSet,0,lastIndex)
4

4 に答える 4

1

The problem isn't recursion. It's just that your first condition is always true: endingIndex is always greater than beginningIndex. That condition returns without recursion, so the function ends there.

于 2012-09-22T17:39:16.350 に答える
0

You can do that using for loop like :

def find_index_equal_value(set):
    for i in range(0, len(set)):
        val = set[i]
        if(val == i):
           print "Index matches value."
于 2012-09-22T17:38:05.067 に答える
0

First of all you must add return to the start of line 48.
Second, add print to start of last line.

于 2012-09-22T17:42:36.647 に答える
0

Firstly, if you can't see what happened, it's because you need to print the returned string:

print FindIndex(sampleSet,0,lastIndex)

Now, if I run it I get:

beginningIndex: 0, endingIndex: 9
midpointIndex: 4.0, midpoint: -3
There is no value in this set such that a[i] = i

which means this if matched:

# check whether ending index is greater then beginning index
if (endingIndex > beginningIndex):
    return "There is no value in this set such that a[i] = i"

... well, of course it did - endingIndex should always be greater than beginningIndex!

For future reference, did you print the string? Did you see the output line and not understand why it took that branch? Did you try stepping through the code with pdb?

于 2012-09-22T17:43:22.213 に答える