## 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.

In Python.

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;

}

Also Java, using binary search:

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)

Python Binary Search

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