request code for a non-recursive binary search in MIPS

[kS_100]

Dear all,
in order to fulfill my report on how to improve the performance of non-recursive binary search in MIPS, I need the code for a non-recursive binary search in MIPS. please help me with providing either the code or any source i can utilize to aquire the code. big thanks in advance.

[Duoas]

Sorry to say, no one here is going to give you code.

Frankly, if you plan to write a report on how to improve code, you need to have a pretty good idea of how the code is generally implemented to begin with. You should be able to write it in your sleep.

I recommend spending some time on Google and finding at a bare minimum two different methods of doing a non-recursive binary search. Study them (if they are not in MIPS, pick your favorite one and convert it to MIPS) and figure out their strengths and flaws.

You might also want to spend some time over at the Wikipedia. The article there is very complete.

Be sure to list everything you find in your references.

Good luck.

[kS_100]

Hi, Duoas, should i understand "a bare minimum two different methods of doing a non-recursive binary search" you mentioned to be different algorithms? if yes, i already got them. and the problem i have now is that i need help to bring up an implementation of the algorithm in MIPS.

The algorithm I understand the best is as below:

BinarySearch(A[0..N-1], value) {
low = 0
high = N - 1
while (low <= high) {
mid = (low + high) / 2
if (A[mid] > value)
high = mid - 1
else if (A[mid] < value)
low = mid + 1
else
return mid // found
}
return -1 // not found
}

any idea to provide some MIPS code to it?

anyway, i appreciate a lot for your sincere words which are showing you are willing to help!!

[Duoas]

You might want to tell your compiler to produce MIPS assembly output for your code. If you are using GCC you can use the -S option. If you are compiling on a machine other than a MIPS processor, you will have to use a GCC that has cross-compiler capabilities and use the -march and -b options.

This would give you a good idea of how such a routine would normally look in assembly.

You might also just want to code it yourself. Have you ever programmed in assembly before?

[venom61991]

Hi guys I need help with kind of the same thing but I wrote most of it, I want to write a subroutine that performs a recursive binary search on an ordered array of 16 bit two's complement words.
I do not know how to start coding it now. Can some one give me a hint on what to do now? What I have now is it tells me "enter a number to begin searching" Please any help would be great Im still learning this. This is mortorlla 68k in assembler.

start:  initIO
        lineout     title
again:  lineout     skipln
        lineout     ask

        pea         buffer
        jsr         getInput
        adda.l      #4,SP
        bvc         OK
        lineout     bad
        bra         again

OK:     move.w      DATA,D1
        subq.l      #1,D1
        andi.l      #$0000FFFF,D1
        asl.w       #1,D1
        lea         array,A1        
        adda.l      D1,A1
        pea         (A1)
        pea         array
        move.w      D0,-(SP)
        jsr         binSearch
        adda.l      #10,SP
        bvc         next
        lineout     n_found
        bra         done
next:   movea.l     D0,A1
        suba.l      #array,A1
        move.l      A1,D0
        asr.l       #1,D0
        addq.l      #1,D0
        cvt2a       position,#6
        stripp      position,#6
        lea         position,A1
        adda.l      D0,A1
        clr.b       (A1)
        lineout     found     

done:   break        

*
*----------------------------------------------------------------------
*       Storage declarations
title:      dc.b    'Program #4, Main program by Alan Riggins',0
found:      dc.b    'The element was found at position #'
position:   ds.b    8
n_found:    dc.b    'The element was not found',0
ask:        dc.b    'Enter the element to search for',0
bad:        dc.b    'Sorry, your input was invalid',0
buffer:     ds.b    82
skipln:     dc.b    0
          end