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.
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.
[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))\$ 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
Passed 6 Test cases: Test Cases #1 Input: ,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