I was asked this question from online coding interview and I have provided my solution that passes all of the test cases. I wanted to see if someone can review my code.
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] == 2
input: arr = [-1,0,3,6] output: -1 # since no index in arr satisfies arr[i] == i.
[input] array.integer arr [output]: interger
I think you can find this question through this link.
My implementation uses binary search, which gives me \$O(Log(N))\$\$O(\log(N))\$ time complexity, and space complexity is \$O(1)\$ in my solution.
def index_equals_value_search(arr):
left = 0
right = len(arr) - 1
ind = 0
last = -1
while left < right:
ind = (left + right) // 2
if arr[ind] - ind < 0:
left = ind + 1
elif arr[ind] == ind:
right = ind - 1
last = ind
else:
right = ind - 1
if arr[left] == left:
return left
return last
Test cases:
Passed 6 Test cases:
Test Cases #1
Input: [0],Expected: 0,Actual: 0
Test Case #2
Input: [0,3],Expected: 0,Actual: 0
Test Case #3
Input: [-8,0,1,3,5],Expected: 3,Actual: 3
Test Case #4
Input: [-5,0,2,3,10,29],Expected: 2,Actual: 2
Test Case #5
Input: [-5,0,3,4,10,18,27],Expected: -1,Actual: -1
Test Case #6
Input: [-6,-5,-4,-1,1,3,5,7],Expected: 7,Actual: 7
