Find X[i] = i In An Array
July 26, 2013
We have today another of our unlimited supply of interview questions: this one supposedly comes from Amazon:
Given an array X[0..n-1] of integers sorted into ascending order with no duplicates, find an array item that is also its index, so that X[i] = i.
For example, X[3] = 3 in the array shown below:
i 0 1 2 3 4 5
x[i] -3 0 1 3 5 7
Your task is to write a program that finds i. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exericse in the comments below.
Programming Praxis 
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 -1Java:
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;
}
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; }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>
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)
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 += 1Python Binary Search
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)i am a lazy candidate
print map { $_ if ($_==$i++) } qw(-3 0 1 3 5 7);
[/sourcode]
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
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.
The problem states that the array doesn’t have duplicates.
If the array has duplicates, my answer in python wouldn’t work either.
(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))))))
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
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)
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:
And in J:
Though one of these is utterly incomprehensible and the other only mildly so,
they work in the same way.
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
Ruby solution:
array = (0..100).to_a.shuffle
result = array.select { |n| n == array[n] }
This is from my friend also in Python
In php
$a =array(-3,0,2,3,5,7);
for($i=0;$i<count($a);$i++)
{
if($a[$i]==$i)
{
echo $a[$i];
}
}
c solution—>
#include
#include
void main()
{
int arr[20],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();
}
(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