정렬 후 회전된 배열 2.2_(a)

A = [1,2,3,4,5] #대상이 되는 배열

# A : 배열, F : 배열의 처음 원소의 인덱스 번호, E : 배열의 마지막 원소의 인덱스 번호
def SamePosAndVal(A,F,E):
    M = (F+E) // 2                      # 배열의 중간 원소의 인덱스 번호
    if (A[0] == 0):                     # 배열의 처음이 0인 경우에, 0을 return
        return 0
    if (F > E):                         # 배열의 마지막 원소의 인덱스 번호가 배열의 처음 원소의 인덱스 번호보다 작다면,
        return -1                       # 조건에 해당하는 원소가 존재하지 않는다는 반증이기 때문의 -1을 return한다.
    if (A[M] < M):                      # 중간 원소의 인덱스 번호보다 A[M]의 값이 더 작다면, 중간 원소의 앞부분에는 찾는 원소가 존재하지 않는다는 반증이기 때문에
        return SamePosAndVal(A,M+1,E)   # 배열의 중간 원소의부터 마지막 원소까지를 재귀호출의 배열로 사용한다.
    elif(A[M] > M):                     # 위의 반대의 경우, 중간 원소의 앞에 해당하는 원소가 있기 때문에 중간 원소를 기준으로 앞의 남아있는 배열을
        return SamePosAndVal(A,F+1,M)   # 다음 재귀호출의 대상으로 삼는다.
    else:
        return M                        # 그리고 나머지의 경우에는 A[M]과 M의 원소가 같은 경우이기 때문에 조건에 해당하는 원소를 찾은 것이므로 M을 return한다.

print(SamePosAndVal(A,0,len(A)-1))