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.
input: arr = [-8,0,2,5]
output: 2 # since arr == 2
input: 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