Find array index with element equality in Python 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 &amp; 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 &lt;= right:
    ind = (left + right) // 2
    if arr[ind] - ind &lt; 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
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 &lt;module&gt;
    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.


You see how important my first comment was.
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".
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.