Topic awaiting preservation: Java Blues

how would I go about writing a recursive method

public static int search(int a[], int m, int n, int target)

That tries to find "target" among the elements of the array. If it finds it, it's suppose to return the position of the target value.

I'm familiar with doing sorts a little bit but I dont know what to do to make it find a particular thing in the array.

~Sh** happens, wear a diaper

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

On a side note: Recursing is just iteration plus a stack. Therefore, iteration can be simulated via recursion (and essentially is in all 'tail-recursive' languages, which may ommit the stack if it's not needed), and recursion can be simulated via an iteration and a stack.

Why recursion? You could just do this:

[b]public static int[/b] search([b]int[/b][] numbers, [b]int[/b] target)

{

    [b]boolean[/b] found = false;

    [b]int[/b] count = 0;



    while (!found)

    {

        found = (numbers[count] == target) ? true : false;

        if (found) break;

        count++;

    }



    [b]return[/b] count;

}

Someone with a stronger theoretical background than me might know a specific reason to write a recursive function instead of a simple array-traversal loop like this one, but the code I offered will do the job.

edit: fixed off-by-one bug. Code is a bit of a hack, but gets the point across.

Cell 1250 :: alanmacdougall.com :: Illustrator tips

[This message has been edited by Perfect Thunder (edited 03-04-2004).]

I am going to say that he has to recurse the array because that is what the assignment entailed...

But like PT said an array data structure is not one that is suited for recursive querying, it just doesn't make sense. It is an O(n) data structure however you look at it, unless you perform some additional operations on it like a quicksort before you search, which might get you into the O(nlogn) range, but I would have to do some math before I could figure that one out.

From your method declairation I believe you are trying to attempt some kind of search based on a structure that is sorted, this would be an array based tree structure, let me know. For the code I am going to present I am assuming 'm' is the start of the indexes and 'n' is the end.

For example and array of size 10 would be searched via a call to int target = search(array,0,array.length,num); where num is your targeted number. Since you are working with integers I am going to assume you are only in the range of positive integers so that a negitive value being returned would consitute a null. Else wish we would have to throw exceptions in order to make sure that the program operates correctly.

public static int search(int a[], int m, int n, int target){

  if(m >= n) return -1;                          //signifies null value to be returned.

  else if(a[m] == target) return m;        //return the index of the target

  else return search(a,m+1,n,target);    //increment and search again (the recursion)

}

Please note the above code has not been tested. YMMV.

-Dan-

[This message has been edited by WarMage (edited 03-04-2004).]

that helps, thanks guys. Luckily this is graded for effort, so if it looks like it could work then I think i'll still get a good grade. The teacher doesn't really know one way or the other so it's all good. I made an array of 5, 3, 2, 1, and 4 but i didnt know what to use the other ints for so I just improvised

~Sh** happens, wear a diaper

I can actually picture uses of such a search method.

Tree structures can be constructed using arrays.

if you have an array

1,2,3,4,5,6,7,8

You can treat the array like a tree using the following rules (i is the index):
1) 2i+1 is the left node
2) 2i+2 is the right node

The above would then be a tree structure such as the following
<BLOCKQUOTE><FONT face="Verdana, Arial">code:</font><HR><pre>
1 - 3 - 7