Filling an array?

[Shananne DuFrame]

Is there a way to automatically fill an array with int values? Is there a way to do this? I am doing an assignment on programming search alogrithms and reporting the comparisons made for binary and sequential searches. The assignment calls for an array of 1000 elements. I want to fill it with ints 1-1000 in order. Any direction to more information on how to do this would be great.

Thanks,
Shananne

[Ricky Clarkson]

1. Google for "java array tutorial". Read.

2. Google for "java for loop tutorial". Read.

3. Apply new-found knowledge.

[Urs Waefler]

Hi

I think, you can do it with a loop.

for(int i = 0, i<=1000, i++)
array[i];

Regards
Urs

[Ricky Clarkson]

That won't compile.

[Eric Daly]

Well, one could easily figure out that you could assign i to array[i]. This is all I'm going to say about those commas in that for loop. And WATCH your comparison... how many times does that thing loop? Be aware.

[Justin Fox]

int [] a = new int[1000];

for(int i = 0; i<1000;i++)
a[i] = i +1;

i think that'll work.

you can search using binary search

just cut the array in half.. if the current value

is bigger than the a[arraysize/2] use the second
half to search further, otherwise, use the fires half.

and keep doing this till you narrow down the value
wanted.

Justin

by the way, binary is much faster than linear search.
[ April 02, 2007: Message edited by: Justin Fox ]

[Shananne DuFrame]

I got it thanks!

[Shananne DuFrame]

I actually used :

for (int i = 0; i < 1000; i++)
{
list[i] = i;
}

Works fine.

I got binary search to work, but am having problems figuring out how to create a method that uses binary searching, switching to sequential search when the size of the list reduces to less than 15. Gonna go try few more things.

[Eric Daly]

Can't you just have a sequential search method that you can call from your binary search method? In binarySearch(), have a continuous check to see if the number of elements is less than 15, then call sequentialSearch() and return the result. But that assumes you are actually removing the elements from your array or list or whatever you have.

[Shananne DuFrame]

This is what I tried for that but I know it's not right. I'm not getting the right results for this. I tried chainging the header in the if, and got way wacked out comparisons reaching numbers in the thousands. This basically is still giving me the same results as a plain binary search. I'm not really sure where to catch it when the list reduces to 15 or how.

Here's my code I tried so far:

public int binarySeqSearch(int key)
{
int first = 1;
int last = list.length-1;
int mid = -1;
boolean found = false;
comparisons = 0;

while (first <= last &&!found) 
{
         mid = (first + last) /2;
            if (list[mid] == key) 
{
found = true;
               comparisons = comparisons + 1;
               return mid;
            }
            else if (list[mid] < key && key >0 ) 
{
               comparisons = comparisons + 2;
               first = mid + 1;
   if (list.length<15) [B]//This is where I think I need something different???[/B]seqSearch(key);
            }
            else 
{
               comparisons = comparisons + 2;
               last = mid - 1;

}
}return -1;
}

public int seqSearch(int key)
{
      comparisons = comparisons;      
      boolean done = false;
      for (int i = 0; i < list.length; i++) 
{
++comparisons;
        if (list[i] == key) 
         {   // found the key
return i; 
}
if  (list[i] != key) 
{               
            return -1;  
        }
}
return -1;
}    

[Shananne DuFrame]

Opps where I have that 'if' it didn't post right it's suppose to be

 
if (list.length<15)//This is where I think I need something different???
   seqSearch(key);
   

[Ricky Clarkson]

I'm not going to try to read that code properly, because the random indentation makes it look like a child's scribble, but I did spot this rather odd code:

comparisons = comparisons;

That does nothing.

[Ricky Clarkson]

Also, merely calling seqSearch won't make binarySeqSearch return the value that seqSearch returns. For that, you'll need to return the value that seqSearch returns.

 
if (whatever)
    return seqSearch(whatever);

[ April 03, 2007: Message edited by: Ricky Clarkson ]

[Jesper de Jong]

Originally posted by Shananne DuFrame:
I actually used :

for (int i = 0; i < 1000; i++)
{
list[i] = i;
}

Works fine.

But that will fill the array with the numbers 0 to 999, not 1 to 1000, which is what you asked for. Look carefully at Justin's answer above again.

[Eric Daly]

You're on the right track Your code:

if (list.length<15) //This is where I think I need something different???

close, but list.length is always going to be the same. How about (last - first)? You're using first and last as indexes of your list, so the difference between the two should give you the number of elements you are searching.
Then you just need to figure out how to do a sequential search of that subset of your list. Is it possible for you to change the sequential search function to take first and last as parameters along with the key? That way seqSearch() will know what range of your list to search (where to start and where to stop).
Plus, you're right that you need something else along with that test to see if the remaining length is less than 15. You need to call seqSearch(), and then return whatever value it gives you. So to make it easier, just put it in one line:

if ((last - first) < 15) {
return seqSearch(first, last, key);
}

something like that...
[EDIT: Sorry Ricky, I pretty much copied what you said without realizing.]
[ April 03, 2007: Message edited by: Eric Daly ]

[Eric Daly]

Wait, I have to say something about your sequential search code. Basically you're saying "start at 0, iterate through list, one at a time. if the element equals the key, return the index of the current element. but if the element does not equal the key, return -1." This logically will only return 0, if the very first element happens to be equal to the key, or it will return negative one. Wait until you have searched the entire list before you return -1. Which means outside the for loop.

[Shananne DuFrame]

Well I tried this:

 
public int binarySeqSearch(int key)
{
int first = 1;
int last = list.length-1;
int mid = -1;
boolean found = false;
comparisons = 0;

while (first <= last &&!found) 
{
         mid = (first + last) /2;
            if (list[mid] == key) 
{
found = true;
               comparisons = comparisons + 1;
               return mid;
            }
[B]else if (list[mid] < key && key >0 ) 
{
               comparisons = comparisons + 2;
               first = mid + 1;
            }
else if ((last - first) < 15 )
{
comparisons = comparisons + 2; 
return seqSearch(first, last, key, comparisons);
}
            else 
{
               comparisons = comparisons + 2;
               last = mid - 1;
}[/B]
}
return -1;
}

//Method seqSearch does a sequential search when the list is less than 15
public int seqSearch(int first, int last, int key, int comparisons)
{  int i;   
      boolean done = false;
      for ( i = 0; i < list.length; i++) 
{
++comparisons;
done = true;
break; 
}
if  (done) 
return i;        
else 
return -1;
}
   

But it seems anything under 500 gives results of 14 and anything over 500 gives results of 19. I know for the numbers 1000 and 733 the result should be 28 comparisons, not 19. For the number 1 entered I got 14 comparisons like I should have. I'm not sure but when I run debugger on it it seems to work ackwardly in the bolded area. Sorry if it posted out of indentation. I have it indented correctly in my jGrasp window, but when I coy and paste it here it must get messed up?