Self-Organizing Search Program

Question

The homework problem asks to call "find" and "find2" with each digit of the following array. However, I am stuck because I don't understand what the code is doing in the first place. Taken from the text, this program "tests the algorithm for 100 elements with a 'locality' set that comprises 20% of the elements and 30% of the references."

{9,0,0,6,3,9,2,4,5,9,0,0,6,3,9,2,4,5,9,0,0,6,3,9,2,4,5} //A given set repeated 3 times

What I'm told is that:

1. I'm supposed to change the current for-loop bodies
2. I must print out the array that is searched (with the searched digits moved to an earlier position).

What I'm asking for is an explanation of the following. Then I can go on to actually manipulating the code.

1. What exactly is find2 doing?
2. What's going on inside the for-loops in which find and find2 are called?
3. How are the counts 4286 and 3903 (as seen in the Output) obtained? (this may end up being answered in one of the previous questions)

Code:

private static int x[]=new int[100];
public static void main(String[] args){
    Random r=new Random(17);

    //Making the array//
    for(int i=0;i<x.length;i++)x[i]=x.length-i;
    System.out.println(Arrays.toString(x));

    r.setSeed(17);
    // straight search
    for(int i=0;i<x.length*1;i++){
        float p=r.nextFloat();
        int j=(int)(p*79);
        if(p<0.3)find(j%20+1);
        else find(j+21);
    }
    System.out.println(n+" "+count);
    //identical but self-organizing
    r.setSeed(17);count=0;n=0;
    for(int i=0;i<x.length*1;i++){
        float p=r.nextFloat();
        int j=(int)(p*79);
        if(p<0.3)find2(j%20+1);
        else find2(j+21);
    }
    System.out.println(Arrays.toString(x));
    System.out.println(n+" "+count);
}

//Find
private static int find(int target){
    for(int i=0;i<x.length;i++)
        if(x[i]==target){
            count+=i;n++;
            return i;
        }
    return -1;
}
static int count=0,n=0;
static final int NEAR=100/10;

//Find2
private static int find2(int target){
    for (int i=0;i<x.length;i++)
        if(x[i]==target){
            count+=i; n++;
            if(i>NEAR){     //swap to NEAR
                x[i]=x[NEAR];
                x[NEAR]=target;
            } else if(i!=0){    //swap with predecessor
                x[i]=x[i-1];
                x[i-1]=target;
            }
            return i;
        }
    return -1;
}

Output:

[100, 99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84, 83, 82, 81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
100 4286
[99, 100, 97, 96, 98, 92, 93, 91, 94, 95, 5, 84, 56, 46, 86, 52, 83, 87, 49, 82, 3, 78, 45, 53, 44, 75, 74, 6, 2, 71, 85, 69, 18, 7, 19, 68, 64, 81, 62, 12, 88, 16, 4, 57, 90, 61, 55, 70, 63, 51, 50, 73, 48, 47, 1, 89, 79, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 65, 80, 17, 58, 15, 14, 13, 72, 11, 10, 9, 8, 67, 66, 54, 59, 77, 60, 76]
100 3903

Any assistance is most appreciated. Also, please let me know if there's anything wrong with the way I asked this question, as it is my first.

Edit: I tried the following modifications, and the output has changed. But without understanding what the code is doing, I don't exactly know the underlying effects.

private static int y[]={9,0,0,6,3,9,2,4,5,9,0,0,6,3,9,2,4,5,9,0,0,6,3,9,2,4,5}; //placed right under x[]
for(int j=0;j<y.length;j++)find(y[j]); //for the 'straight search' for-loop body
for(int j=0;j<y.length;j++)find2(y[j]); //for the 'self-organizing' for-loop body

Answer 1

1. What exactly is find2 doing?
The self-organizing algo is attempting to organize itself in a fashion such that the more often searched-for items are closer to the front. This way when the array is searched the more often targets can be found quicker on subsequent searches. For example, if you search and find 1 at i = 99, then moving it to NEAR (10) would result in a 10x faster retrieval the second time around. However, just from what I've seen, the idea of creating a sorted array to show this is kind of silly. If you already had a sorted array, say 1 - 100 descending as in your example, you could just check the target and split the array or rather give it directly as x[100-target] and it would indeed give you the target. If it were me, I would have randomized the elements, oh well.

2. What's going on inside the for-loops in which find and find2 are called?
These are just generating *pseudo* random numbers as the targets. They are pseudo so the results are the same each time as the "random" numbers are not so random. They are also limited to the data set as nextFloat() will return a number between 0.0 and 1.0 - p*79 just gives a percentage of 79, then based on p you then calculate the target which will be between 1 and 100.

3. How are the counts 4286 and 3903 obtained?
These are the counts that are trying to show you that you've accomplished what you were trying to, i.e., find data faster. Basically count is an accumulator. Each time a target is found at i, i is added to count. If you had three elements found at i = 1, 2, and 3, count would be 6. The larger is showing the sum of all indexes of the found targets without allowing it to organize itself. The smaller one shows that due to the new organization you were able to improve the search. If no performance was gained the numbers would be the same.

You could store the targets in another array and see how often certain targets are called to relate what you're seeing as output, at first glance it just looks random.