Searching the Array Index & Element Equality

Question

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

Answer 1

I think you've made the right call in going with binary search for this problem. I agree that in terms of asymptotic complexity it is \$ O (log(n)) \$ in time and \$ O(1) \$ in space.

The line ind = 0 is unnecessary because it will be reset 3 lines later before it's ever used.

The implementation seems broadly solid and you have your edge cases covered. I think you could simplify out that last if arr[left] == left: check by changing the loop condition to while left <= right:. That would mean the computer running a couple of unnecessary lines of code going through the loop one last time instead of you writing (and the computer parsing) a couple of unnecessary lines of code checking an edge case. I would probably favour the code uniformity, but there's not much in it.

I think if I was writing that innermost test block I'd do it slightly differently. I'd first check for equality and set last in the case of a match, and then independently (i.e. not in elif) check for which way to search. This just makes it easier to see what you are doing, in terms of record running best and continue search. Something that looks a bit like this

 if arr[ind] == ind:
 last = ind # found a satisfying index. Record it
 if arr[ind] >= ind:
 right = ind - 1 # Navigate left for smallest satisfying index
 else:
 left = ind + 1 # Navigate right for smallest satisfying index

You could possibly do with a couple of comments to help make it clearer what is going on. In particular, I would appreciate a comment explaining what your algorithm is doing at a high level, and where it differs from what I might expect. That is, for example, that it's using binary search, and that it doesn't return immediately on finding a solution because it needs the lowest satisfying number. Also on code clarity, I find the variable name last confusing. What is it the last of? It could either benefit from a comment saying that it's the best satisfying index found thus far, or renaming to that effect.

if arr[ind] - ind < 0: is a slightly strange and unnecessarily complicated way of writing if arr[ind] < ind:. In python it is normally equivalent because python normally uses arbitrary precision integers, but in some cases where it's using a C style fixed length integer representation it could actually give the wrong answer because of integer underflow.

On a very pedantic note, this answer is potentially incorrect half the time because it ignores negative indicies. Python allows indexing to a[-x] to return the xth entry from the end. If your input array is a=[-7, -2, 5] then a[-2]==-2 and -2 is the lowest such index. I think this is a failure on the part of the question setter, and I'm confident that they don't have it in mind because they asked for a failing return code that would otherwise be a legal return code. Probably a case of "Clarify the requirements" in an interview or development situation rather than "Change the code" but it's worth bearing in mind.

• superb rain: "you have your edge cases covered" - Not really, since the most obvious edge case, an empty list, makes them crash.