Question

Python - You are given a sorted (from smallest to largest) array A of n distinct integers which can be positive, negative or zero. Design the fastest algorithm you can for deciding if there is an index i such that A[i] = i.

Answer 1

# Returns index of x in arr if present, else -1

def findElementAlgo (arr, l, r):

# Check base case

if r >= l:

#finding mid element

mid = int(l + (r - l)/2)

#checking if a[i]==i

if arr[mid] == mid:

return mid

# If index is smaller than element at inde, then it can only

# be present in left side

elif arr[mid] > mid:

return findElementAlgo(arr, l, mid-1)

# Else the element can only be present in right side

else:

return findElementAlgo(arr, mid+1, r)

else:

# Element is not present in the array

return -1

# Test array

arr = [ 1,1,4,4]

# Function call

result = findElementAlgo(arr, 0, len(arr)-1)

if result != -1:

print ("A[i]=i exist : ",result)

else:

print ("A[i]=i does not exist")

Note : Please comment below if you have concerns. I am here to help you

If you like my answer please rate and help me it is very Imp for me