使用重复的旋转阵列搜索时输出错误

Question

测试输出时，我发现输出中有错误。将ARR2和X = 3作为我的输入，MID中的值是在上次递归呼叫中的4个。但是，它没有返回中间，而是跳过了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 block

中已经混乱的代码

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 Loop

最后一个代码块应为：

    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)