is this an efficient algorithm?

Hi this is m开发者_C百科y algorithm which takes an array with float numbers that are sorted before.because I have thought that when we sort an array before using this algorithm ;its worst case performance will be O(nlogn) but without sorting it will be O(n^2).So I think that this algorithm will be OK for finding one duplicate number.am I right?thanks

1     Algorithm Duplicate_Number(a , n)
2     // Find one duplicate number in a[1 :n ]
3     {
4              temp: = a [0];
5              while (i<n) do
6              {
7                     if (temp=a[i])
8                     {
9                           return a[i]; break;
10                    }
11                    else
12                         temp: =a [++i];
13           }

Well, you never defined "i", but if your array is sorted, this will work for any totally ordered type- one where there is only one correct sort order for a collection- and float is such a type.

Floats are rarely exactly equal to each other, especially if they went through any actual steps of calculation beforehand. It is usually better to do a check for if floating point numbers are within a small range of each other, to handle some of the inevitable error in the calculations due to rounding. If you aren't doing computing steps ahead of time and are just taking input, this should work.

Are you familiar with hash tables? This problem can be solved in O(n) time. You don't need the array to be sorted, so you don't spend O(n lg n) time sorting it. For each element, check if it is already in the hash table; return it if it is, and insert it into the hash table if it isn't. Insert and read operations are O(1) (amortized, and assuming a good hash function) on a hash table, so that should meet your needs. A hash table cannot do the approximate-equality match, though- hash tables are only useful for exact value lookups, because they don't keep data in a sorted order.

A fully generic Java implementation that should work for any type that defines a meaningful hash function and a meaningful equals (assuming Object's default reference behavior is wrong):

import java.util.HashSet;

class DuplicateValue{
    public static <T> duplicateValue(T[] values){
        HashSet<T> store = new HashSet<T>();
        for(T item : values){
            if(store.contains(item)){
                return item;
            }
            store.add(item);
        }
        return null; //no duplicate found
    }
}

This works for literally any data type, since Java provides built-in HashCode and Equals functions. That said, if you're using a custom data type, be sure to override .hashCode and .equals so this provides meaningful results. float isn't an object, but it can be autoboxed into Float, which is.

In theory, the algorithm could be made O(n) by storing all numbers inspected so far in a hash and looking it up on every iteration. Given look-ups are O(1), it can be considered faster.

In practice, speedup depends on the speed of the hash function and memory available for storing the additional data.

You didn't initialize i.

Once that is done, go through an array, comparing each two 'neighbours'.

Also, since you're using floats, you might want to consider if some two numbers are close enough... This isn't necessary for your algorithm, though, but if those numbers are generated by some calculations, it might be useful. You could, for example, use some epsilon = 0.000000000000000001 or smt.

So, algorithm very similar to yours might be:

i:= 1
tmp:= a[0];
while(i < n) {
    if(a[i] = tmp) {
        print "duplicate number: " + tmp
        break
    } else {
        tmp:=a[i]
        i++
    }
}

P.S. And yes, sorting an array is a good idea. This chunk of code has complexity O(n) when sorted array is used.

Performance is going to be a lot better than you expect, given the bug that forces it to always finish after the first iteration of the loop. I think you want i++, not ++i.

A simpler for loop will be just as efficient, but much more readable:

for(int i=1; i<n; i++)
{
  if(a[i] == a[i-1])
    return a[i];
}

Edit:- This example uses C syntax, but most languages have a for loop equivalent.