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.

About these ads

Pages: 1 2

21 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[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();

    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 574 other followers

%d bloggers like this: