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))\$ 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