alright, i have this program due in my mips class that is a rewrite of an older program i did just this time with slightly different requirements and i don't really understand exactly how i should be modifying my old code so any help on explaining this better or getting me started would help me out very much description: redo program 2, but using a recursive binary search algorithm. in this case, clearly the array's elements must be sorted in ascending order requirements: your program must use a recursive function to do the search the function is to be passed four parameters: 1. the base address of the array to search 2. the lowerbound index for the search space 3. the upperbound index for the search space 4. the target value to search for the function must return -1 on failure and the index of target on success i can post up my old code if that would help anyone...thanks in advance

In a binary search, you divide a set of data into two halves, then check whether what you're searching for is above the middle or below the middle. Then you do it again with the side it's on, and again and again until you either find what you're searching for or determine that it's not in the set. I don't know ASM, so I can't help with the actual coding, but hopefully that helps you

since you obviously know c pretty well...is there any chance you can give me an example of this in c++ because i've been trying to think of how to divide the array into 2 halves so basically my last program was to search for and find a value in an unordered array using a linear search now is this new program something that can just be rewritten from my old one easily or does doing a recursive binary search algorithm something that will change basically every part of the program? because to me it seems that it is pretty similar

A binary search only works if the array is sorted. It works like this: 1) Given a lower and upperbound index within which to search, the first thing to do is check if lowerbound == upperbound in which case the search function is being asked to look at only one element in the array. Check if array[lowerbound] == targetvalue and return either -1 or lowerbound. 2) If lowerbound < upperbound check the midpoint element (i.e. the element at index (lowerbound + upperbound)/2). Since the array is sorted, if the value of the midpoint element is less than targetvalue, then search again in the upper half of the array bounded by midpoint+1 and upperbound. If the midpoint is greater than the target value, then search again in the lower half of the array bounded by lowerbound and midpoint. Step 2 is where it gets recusive because the search function is calling itself with different array bounds. The description should be enough for you to come up with your own C/C++ code which you can use to translate to ASM.

but based on that...i don't understand how to make my array split into a lowerbound and upperbound...do i just have 2 seperate arrays? also something i forgot to mention is that i program in what is in the array...when the program is run, the user inputs a value and the program returns what spot in the array the target value is at

The upper and lowerbound are just array indices that define a range in which to search. You're not creating two new arrays, you're just logically dividing the array by defining two separate ranges. Suppose you have a 10 element array. To search the entire array, the lower and upperbound would be 0 and 9 respectively. The algorithm says compare the targetvalue with the element at the midpoint of the range. In this case (0 + 9)/2 = 4. So compare array[4] with target value. If targetvalue is greater, then if targetvalue is contained in the array, it must be somewhere between index 5 and 9. So, you call the search function recursively using 5 and 9 as the lower and upperbound. If targetvalue is less, then search the range from 0 to 4. This process continues until you reach a point where lower and upperbound are the same, so you've narrowed your search to one element. Now if this element is equal to the targetvalue, you return the index, otherwise return -1.

i'm not writing it in c but most people you talk to will reccomend that you write ASM instructions in a high level language first and then transfer it over

really?? in my sparc assembly class we just wrote psuedo-code for the algorithm, and then programmed from there....

skinjob...hope you're still on this late at night...or anytime in the morning before i wake up how does this look for the c++ version of the code? i came up with one while i was at work tonight but then i went searching online and found another one that is semi-different...of course i just wrote these and then coded them in using wordpad so the formatting is probably gonna be off int bsearch(int array[], int lower, int upper, int target) { int mid; if(lower > upper) return -1; mid = (upper + lower)/2; if(array[mid] == target) return array[mid]; else if(array[mid] > target) return bsearch(array, lower, mid-1, target); return bsearch(array, mid+1, upper, target); } here is the other one i found online void binary_search(apvector <int> &array, int lowerbound, int upperbound, int key) { int search_pos; search_pos = (lowerbound + upperbound) / 2; while((array[search_pos] != key) && (lowerbound <= upperbound)) { if(array[search_pos] > key) { upperbound = search_pos - 1; } else { lowerbound = search_pos + 1; } search_pos = (lowerbound + upperbound) / 2; } } now...i talked to my professor this afternoon and he said i should be using stacks for this program...i have no idea how stacks would relate to this at all...any ideas? and do you have any tips on converting this over to mips? i usually have trouble with that my mips program is due on wednesday or later (it is supposed to be due wednesday but the professor is fairly flexable and doesn't take off too many points if it's late)...but i'd like to get it done by wednesday if at all possible...so do you have any pointers on transferring this over to mips? thanks again for all the help

Your function looks like it should work. The second function you found isn't recursive. You don't need a stack data structure to implement the search algorithm, but since you are trying to write assembly language code that calls a function (itself), your prof maybe talking about the call stack. I don't remember much of asm, but I know you need to push function arguments onto the call stack and maybe a return address before you jump to the function address. Your code should be pretty simple. Compare the arguments, and if needed, push the appropriate arguments onto the call stack and call (jump) the function recursively.

skinjob is right, all arguments to functions in assembly code are pushed onto the stack. To execute a function, call the jal (jump and link) instruction to whatever pc address you decide to start you function. Then, do a jr (jump register) to whatever register is written by the jal instruction to return from your function call.

is there any way you can give me an example of how to even push a stack in mips...like what the command could be?

Here's something I found on google http://www.cs.sunysb.edu/~cse320/example.html Take a look at example 2: There is a register called the stack pointer that contains the current address of the top of the stack. In MIPS, it looks like it's called $sp. You just copy the value you want to push on the stack to the address pointed to by $sp, then move the stack pointer so it points to the next available spot on the stack.

alright, i'm getting into writing the program and don't know how to do a mips statement splitting the main array into 2 parts...how do you do division in mips? i am only finding addition and subtraction

nevermind...found how to do division now i am having trouble indexing into the array...like how do i say the array divided by 2 and if the input is less than that value to do something...and if the input is greater than it to do something else