# A resursive procedure to accumulate a sum
* Binary search is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful.
* Below is a simple implematation of recursive binary search in C:

int binarySearch(int arr[], int l, int r, int x) 
    { 
        if (r >= l) { 
            int mid = l + (r - l) / 2; 
  
            // If the element is present at the middle itself 
            if (arr[mid] == x) 
                return mid; 
  
            // If element is smaller than mid, then it can only 
            // be present in left subarray 
            if (arr[mid] > x) 
                return binarySearch(arr, l, mid - 1, x); 
  
            // Else the element can only be present in right 
            // subarray 
            return binarySearch(arr, mid + 1, r, x); 
        } 
  
        // We reach here when element is not present in array 
        return -1; 
    } 

* And my risc-v implementation of binary search:

# s0: base address of array
# s1: array size
# s2: the search element
# return index at $a5,if search element not found , put -1 in a5

.data
success1: .string "search success "
success2: .string " at index "
fail_string1: .string "search element "
fail_string2: .string " does not exist!"
array:   .word 1, 4, 5, 7, 9, 12, 15, 17, 20, 21, 30
array_size: .word 11
search_element:.word 9
.text
main:
    # binarySearch(int arr[], int l, int r, int x)  
    addi t0, zero, 0    #int l
    la   t1, array_size  
    lw   t1, 0(t1)      #int r
    addi t1, t1, -1
    add  s10,t1,zero   # s10 used to check if search is go out of bound of array
    addi a5, zero, -1
    la   s2, search_element
    lw   s2, 0(s2)              #s2 stands for search value
    la   s0, array           # load the base address to $s0
    jal  ra, binary_search      # Jump-and-link to the 'binarySearch' label
    bltz a5, Fail				#check if found or not
    j exit
binary_search:
    # a2 stand for mid = (l + r)/2
    add  a2, t0, t1
    srli a2, a2, 1
    #check if mid > array_size
    blt s10,a2,Fail
    #check if mid < 0
    bltz a2,Fail
    # check if array[mid]== search_element
    add  t2, a2, zero
    slli t2, t2, 2 # t2=t2*4
    add  t2, t2, s0 
    lw   t2, 0(t2)
    beq  t2, s2, Find
    # check if to == t1 and still not equal
    beq t0,t1,Fail
    #not equal then adjust l,r depends on the value of array[mid]
    blt  s2, t2, less
greater: #elseif target > array[mid] : l = mid + 1
    addi t0,a2,1
    j binary_search
less: # @if target<array[mid] : r = mid-1
    addi t1,a2,-1
    j binary_search
    ret
Fail:
    addi a5,zero,-1
    la  a1, fail_string1
    li  a0, 4
    ecall

    mv       a1, s2
    li       a0, 1
    ecall

    la  a1, fail_string2
    li  a0, 4
    ecall
    j exit
Find:
    add a5,a2,zero
    la  a1, success1
    li  a0, 4
    ecall

    mv       a1, s2
    li       a0, 1
    ecall

    la  a1, success2
    li  a0, 4
    ecall

    mv       a1, a5
    li       a0, 1
    ecall
    
    j exit
exit: