Find array index with element equality in Python

Question

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.

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.

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

Answer 1

Better tests

Before anything, let's improve the test suite so that we can feel more confident updating the code.

At the moment, the tests:

• rely on meaningless values printed on standard output which have to be compared to values in the comments - we'll see quickly why this is something to avoid

• have somes values "untested": value for test1 is not printed

• have variables with names that does not convey much meaning (testXXX)

Let's see how we can improve this. We could:

• get rid of the testXXX variables

• rename all arrYYY variables as arr

• use assert to checking everything is working properly. If we want to do things properly, we could use a unit test framework such as unittest.

At this stage, we have:

def test_index_equals_value_search():
    arr = [-8,0,2,5]
    assert index_equals_value_search(arr) == 2
    arr = [-1,0,3,6]
    assert index_equals_value_search(arr) == -1
    arr = [0,1,2,3]
    assert index_equals_value_search(arr) == 0
    arr = [-6,-5,-4,-1,1,3,5,7]
    assert index_equals_value_search(arr) == 7

which gives:

Traceback (most recent call last):
  File "review212877.py", line 32, in <module>
    test_index_equals_value_search()
  File "review212877.py", line 28, in test_index_equals_value_search
    assert index_equals_value_search(arr) == 0
AssertionError

My job pretty much stops at this point but I'll give additional comments anyway.

1. You see how important my first comment was.

2. This error also shows something which is missing in your code: documentation. Indeed, the value returned is correct if we stricly refer to the function name. However, there should be a piece of docstring mentionning we want "the lowest index".

3. Algorithms relying on indices and in particular binary search are very easy to get wrong and are not always easy to test. However, a function doing the same thing using linear search is very easy to write. If I were you, I'd write such a function and use it to write a pseudo-oracle:

def index_equals_value_search_linear(arr):
    for i, x in enumerate(arr):
        if i == x:
            return i
    return -1

More comments

Style

Python has a style guide called PEP 8 which is worth reading and trying to apply.

Among other things, it says:

Use 4 spaces per indentation level.