I was given this question during an interview. It is similar to binary search and I would like to ask for feedback for my solution.
Array Index & Element Equality
Given a sorted array arr of distinct integers, write a function indexEqualsValueSearch that returns the lowest index i for which arr[i] == i. Return -1 if there is no such index. Analyze the time and space complexities of your solution and explain its correctness.
Examples:
input: arr = [-8,0,2,5]
output: 2 # since arr[2] == 2input: arr = [-1,0,3,6]
output: -1 # since no index in arr satisfies arr[i] == i.
def index_equals_value_search(arr):
left = 0
right = len(arr) -1
ind = 0
output = -1
while left <= right:
ind = (left + right) // 2
if arr[ind] - ind < 0:
left = ind + 1
elif arr[ind] == ind:
output = ind
break
else:
right = ind -1
return output
Passing all of the basic tests
arr = [-8,0,2,5]
test1 = index_equals_value_search(arr)
arr2 = [-1,0,3,6]
test2 = index_equals_value_search(arr2)
print(test2) # return -1
arr3 = [0,1,2,3]
test3 = index_equals_value_search(arr3)
print(test3) # return 0
arr4 = [-6,-5,-4,-1,1,3,5,7]
test4 = index_equals_value_search(arr4)
print(test4) #return 7
break
is not a copy-paste error? \$\endgroup\$