binarysearch.R

#' ---
#' title: "Binary Search in R"
#' author: "Rahul Goswami"
#' ---


#' Binary Search is a searching algorithm that is used to find an element in a sorted array.
#' The basic idea of binary search is to search for an element in a sorted array by repeatedly dividing the search interval in half.
#' The average case time complexity of binary search is O(log n)  
#' The worst case time complexity of binary search is O(n)  
#' The best case time complexity of binary search is O(log n)  (if the array is already sorted)  
#' The space complexity of binary search is O(1)  (in-place)   
#' 
#' ### Algorithm:
#' 1. Find the middle element of the array
#' 2. If the middle element is the element to be searched, return the index of the middle element
#' 3. If the middle element is greater than the element to be searched, search the first half of the array
#' 4. If the middle element is less than the element to be searched, search the second half of the array  


#' @param vec Vector to be searched  
#' @param element Element to be searched  
#' @return Index of the element  
 


binary.search <- function(vec, element){
    # Find the middle element of the array
    mid <- length(vec)/2
    # If the middle element is the element to be searched, return the index of the middle element
    if(vec[mid] == element){
        return(mid)
    }
    # If the middle element is greater than the element to be searched, search the first half of the array
    if(vec[mid] > element){
        return(binary.search(vec[1:mid], element))
    }
    # If the middle element is less than the element to be searched, search the second half of the array
    if(vec[mid] < element){
        return(mid + binary.search(vec[(mid+1):length(vec)], element))
    }
}

#' ### Example
sorted_vec <- c(0,1,2,3,4,5,6,7,8,9)
binary.search(sorted_vec, 5)