## Find X[i] = i In An Array

### July 26, 2013

One solution uses linear search through the array:

```(define (f x)   (let loop ((i 0))     (cond ((= i (vector-length x)) -1) ; not present           ((= i (vector-ref x i)) i) ; found solution           (else (loop (+ i 1)))))) ; try next element```

If you gave that answer, you probably wouldn’t make it to the next round of interviews. A better solution uses binary search, so it takes O(log n) instead of the O(n) of the linear search:

```(define (f x)   (let loop ((lo 0) (hi (- (vector-length x) 1)))     (if (< hi lo) -1 ; not present       (let ((mid (quotient (+ lo hi) 2)))         (cond ((< (vector-ref x mid) mid)                 (loop (+ mid 1) hi))               ((< mid (vector-ref x mid))                 (loop lo (- mid 1)))               (else mid)))))) ; found solution```

This function will find an answer if multiple elements of the array all equal their indices, but not all answers; it will also work in the face of duplicate array elements. However, it will not work if the array elements are not sorted into ascending order; in that case, the only solution is linear search.

You can run the program at http://programmingpraxis.codepad.org/cqxBWBKj.

Pages: 1 2

### 22 Responses to “Find X[i] = i In An Array”

1. Paul said

In Python.

```def find(arr):
"""returns i if arr[i] == i else -1"""
lo, hi = 0, len(arr)
while lo < hi:
i = (lo + hi) // 2
ai = arr[i]
if ai == i:
return i
elif ai > i:
hi = i
else:
lo = i + 1
return -1
```
2. Steve said

Java:

public static int findIndexMatchingValue(int[] x) {
int i = 0;
while(x[i] != i) {
if(x[i] > i) {
return -1;
} else if(x[i] < i) {
i++;
}
}
return i;
}

3. Steve said

Also Java, using binary search:

```public static int findIndexMatchingValue(int[] x){
int i = 0;
int max = x.length - 1;
int low = 0;
while(x[i] != i){
if(i > max || i < low){
i = -1;
break;
}
if(x[i] > i){
max = i;
i -= i / 2;
} else if(x[i] < i) {
low = i;
i+= (x.length - i) / 2;
}
}
return i;
}
```
4. This is solved trivially with a dichotomy indeed. But why would you have to copy-and-paste it again? Nobody teaches that copy-and-paste coding is bad?

``` cl-user> (let ((v (vector -3 0 1 3 5 7)))            (com.informatimago.common-lisp.cesarum.utility:dichotomy             (lambda (index)               (cond ((= index (aref v index)) 0)                     ((< index (aref v index)) -1)                     (t +1)))             0 (1- (length v)))) t ; found 3 ; index 0 ; order (in case not found) cl-user> ```

5. Someone said

Python:
def findI(array, start, end):
if(start >= end):
if(array[start] == start and start==end):
print (array[start])
return

i = (start+end)//2;
y = array[i];
if(y>i):
findI(array, start, i-1)
elif(y==i):
findI(array, start, i-1)
print (i)
findI(array, i+1, end)
elif(y<i):
findI(array, i+1, end)

6. Marcos said
```def search(arr):
index = 0
while True:
if index > len(arr):
return -1
if index == arr[index]:
return index
if index < arr[index]:
index = arr[index] + 1
else:
index += 1
```
7. Someone said

Python Binary Search

8. Eh said
```def findI(array, start, end):
if(start >= end):
if(array[start] == start and start==end):
print (array[start])
return

i = (start+end)//2;
y = array[i];
if(y>i):
findI(array, start, i-1)
elif(y==i):
findI(array, start, i-1)
print (i)
findI(array, i+1, end)
elif(y<i):
findI(array, i+1, end)
```
9. novatech said

i am a lazy candidate

print map { \$_ if (\$_==\$i++) } qw(-3 0 1 3 5 7);
[/sourcode]

10. jrapdx said

Well, not too hard in Scheme:

(“array” modeled by list)

(define (pos= arry-ls)
(let lp ((ls arry-ls) (n 0))
(if (null? ls)
#f
(if (= n (car ls))
n
(lp (cdr ls) (+ n 1))))))

Running a test…

(define arry ‘(-2 0 5 3 9 1)) ;; list elem at index 3 equals 3

(pos= arry) => 3

(define arry ‘(-3 0 1 1 6 7)) ;; no list elem equals its index

(pos= arry) => #f

11. Marek Sotola said

The posted scheme solution doesn’t work if the array has duplicates (as stated in the solution): try -1 2 3 4 5 5 8.

12. Eh said

The problem states that the array doesn’t have duplicates.
If the array has duplicates, my answer in python wouldn’t work either.

13. root@example.org said

(define [find ary left right]
(if [= (vector-ref ary left) left]
left
(if [>= left right]
-1
(let* ([mid (quotient (+ left right) 2)]
[val (vector-ref ary mid)])
(if [< val mid]
(find ary (+ mid 1) right)
(find ary left mid))))))

14. Kaushik said

Scala,

def find(x : List[Int]) : String = x.zipWithIndex filter (e => e._1 == e._2) map {_._1} mkString(“,”) match {
case “” => “-1”
case str => str
}

find(-3 :: 0 :: 1 :: 3 :: 5 :: 7 :: Nil) // 3
find(-3 :: 0 :: 1 :: 5 :: 5 :: 7 :: Nil) // -1
find(-3 :: 2 :: 2 :: 3 :: 6 :: 5 :: Nil) // 2,3,5

15. Rudi Grinberg said

OCaml solution:

let find_i arr =
let rec f low length =
if length – low = 0 then None
else
let mid = (length + low) / 2 in
if arr.(mid) = mid then Some(mid)
else if arr.(mid) > mid then f low mid
else f mid length
in f 0 (Array.length arr)

16. Graham said

A bit late to the party, but I’ve been meaning to learn more R and have been
intrigued by array languages like J for a little while know. I’ll write up a
post on my new blog explaining these answers soon, but here are my submissions.

First, in R:

```xs <- c(-3, 0, 1, 3, 5, 7)
xs[xs==seq(length(xs))-1]
```

And in J:

```(I.@:=i.&#) _3 0 1 3 5 7
```

Though one of these is utterly incomprehensible and the other only mildly so,
they work in the same way.

17. Roberto Bravo said

Python

array = [ -3 , 0 , 1 , 3 , 5 , 7 ]
count = 0

for integer in array : if array[count] == integer and count == integer: print integer else : count = count + 1

18. Giovanni Salcedo said

Ruby solution:

array = (0..100).to_a.shuffle
result = array.select { |n| n == array[n] }

19. Roberto Bravo said

This is from my friend also in Python

```res = [x for idx, x in enumerate(myList) if x == idx]
```
20. In php
\$a =array(-3,0,2,3,5,7);

for(\$i=0;\$i<count(\$a);\$i++)
{
if(\$a[\$i]==\$i)
{
echo \$a[\$i];
}

}

21. vibhumishra007 said

c solution—>
#include
#include
void main()
{
int arr,a,result=-1;

printf(“enter the no of element”);
scanf(“%d”,&a);

printf(“enter the numbers”);

for(int i=0;i<a;i++)
scanf("%d",&arr[i]);

for(i=0;i<a;i++)
{
if(arr[i]==i)
{
result=i;
break;
}
}

if(result!=-1)
printf("result is %d",result);

else
printf("no match found");

getch();

}

22. arthuruncle said

(defun bisearch-fixed-point (arr)
(defun bisearch-iter (index)
(cond ((= index (aref arr index)) index)
((< index (aref arr index)) (bisearch-iter (/ index 2)))
(t (bisearch-iter (+ index (/ index 2))))))
(bisearch-iter (/ (length arr) 2)))

;; (bisearch-fixed-point [-3 0 1 3 5 7])

;; 3

;; (bisearch-fixed-point [-3 0 1 2 4 7 9])

;; 4