在具有重复项的旋转数组中搜索时输出错误

Question

在测试输出时，我发现输出中有一个错误。使用arr2和x=3作为我的输入，在最后一次递归调用期间，mid的值应该是4。但是，它没有返回mid，而是跳过if语句，并在末尾返回False。有人[在此输入图像描述][1]看到我在这里做错了什么吗？多谢各位

class rotatedArraySearch:
    #similar to binary search
    def rotatedAS(self,arr,x,low,high):
        mid = (low + high)/2
        print mid
        if x == arr[mid]: return mid

        if low > high: return False

        #check which side is ordered properly
        if arr[low] < arr[mid]:
            #if the left side is ordered properly, check if it is in the left side, if not search right
            if x >= arr[low] and x < arr[mid]: return self.rotatedAS(arr,x,low,mid-1)


            else: return self.rotatedAS(arr,x,mid+1,high)

        elif arr[mid] < arr[low]:
            #same for right side
            if x > arr[mid] and arr <= arr[high]: return self.rotatedAS(arr,x,mid+1,high)


            else: return self.rotatedAS(arr,x,low,mid-1)

        #if there are duplicate values the order is not known, check both sides
        elif arr[low] == arr[mid]:
            if arr[mid] != arr[high]: return self.rotatedAS(arr,mid+1,high,x)


            else:
                result = self.rotatedAS(arr,low,mid-1,x)
                if(result == False): return self.rotatedAS(arr,mid+1,high,x)


                else: return result

        return False
#test
arr = [5,6,7,2,3,4]
arr2 = [2,2,2,2,3,4,1]
ras = rotatedArraySearch()
print ras.rotatedAS(arr2,3,0,len(arr2)-1)

Answer 1

您在最后一个elif块中弄乱了代码

if arr[mid] != arr[high]: return self.rotatedAS(arr,mid+1,high,x)
if(result == False): return self.rotatedAS(arr,mid+1,high,x)

result = self.rotatedAS(arr,low,mid-1,x)

换成

• if arr[mid] != arr[high]: return self.rotatedAS(arr,x,mid+1,high)
• if(result == False): return self.rotatedAS(arr,x,mid+1,high)
• result = self.rotatedAS(arr,x,low,mid-1)

请注意x是搜索值，您在最后一个elif循环中将其作为高值传递

最后一个代码块应为：

    elif arr[low] == arr[mid]:
        if arr[mid] != arr[high]:
            #Change here
            return self.rotatedAS(arr, x, mid + 1, high)
    else:
        ##Change here
        result = self.rotatedAS(arr,x , low, mid - 1)
        if not result:
        #Change here
            return self.rotatedAS(arr, x, mid + 1, high)
        else:
            return result

    return False

输出：

x=3 mid value=2 at pos 3 
x=3 mid value=4 at pos 5 
x=3 mid value=3 at pos 4 
4

注：追踪

print 'x={} mid value={} at pos {} '.format(x, arr[mid], mid)