R/BinarySearch_onListOfNumericVectors.R

In msxakk89/dat: Data Analyst Toolkit (dat): a library of tools for data analysts and scientists

#' Perform binary search on list of numeric vectors using query numeric vectors
#' 
#' This is a generic function to perform binary search of log2(n) time complexity to search a list of SORTED numeric vectors (in increasing order) and retriving their keys.
#' 
#' Binary search requires a sense of ordering (thus uses recursion).
#' The order is defined by the left-most member of the numeric vector that differs between the two neighbouring vectors. For example [c(1,1,1), c(1,1,2), c(1,2,1)] is in order but [c(1,1,1), c(1,2,1), c(1,1,2)] is not (becasue the left-most number differing is 2 in the second element which should be a third element to be considered ordered).
#' A numeric vector supersedes (comes after) another numeric vector if the left-most differeing number between the two vectors is higher in value.
#' 
#' 
#' @param VecToBeQueried Numeric vector to be queried
#' @param lst_ofSortedVecs List of numeric vectors sorted by values in increasing order
#' @return A numeric key index of lst_ofSortedVecs corresponding to query. NA is returned if VecToBeQueried is not in lst_ofSortedVecs.
#' @export  


binarySearch_onListOfNumericVectors = function(VecToBeQueried, lst_ofSortedVecs,left_index = 1,right_index = length(lst_ofSortedVecs), verbose=F){
  ############ For testing
  #print(paste("left_index=",toString(left_index)))
  
  #print(paste("right_index=",toString(right_index)))
  
  # print("lst_ofSortedVecs:")
  # print(lst_ofSortedVecs[left_index:right_index])
  ############
  # 1. If L > R, the search terminates as unsuccessful.
  if(left_index > right_index){
    if(verbose){
      print("Message from binarySearch_onListOfNumericVectors: query not found")
    }
    return(NA)
  }
  # 2. Setting middle/pivot index
  middle_index = floor(
    (left_index+right_index)/2
  )
  
  pivot_case = lst_ofSortedVecs[[middle_index]]
  
  #print(paste("middle_index=",toString(middle_index)))
  #print("Pivot case:")
  #print(pivot_case)
  #print("VecToBeQueried:")
  #print(VecToBeQueried)
  
  # 3. Determining whether pivot_case (1) or VecToBeQueried (2) have a higher rank
  which_is_higher = WhichOfTheTwoNumericVectors_hasHigherRank(list(as.numeric(pivot_case),as.numeric(VecToBeQueried)))
  #print("which_is_higher:")
  #print(which_is_higher)
  
  # 4.1 If pivot_case has a lower rank than set the search window using left_index = pivot_index and right_index and run recursively
  if(which_is_higher==2){
    left_index = middle_index + 1
    return(
      binarySearch_onListOfNumericVectors(VecToBeQueried=VecToBeQueried,
                                          lst_ofSortedVecs=lst_ofSortedVecs,
                                          left_index = left_index,
                                          right_index = right_index)
    )
  }
  # 4.2 If pivot_case has a higher rank than set the search window using left_index = 0 and right_index = pivot_index and run recursively
  if(which_is_higher==1){
    right_index = middle_index - 1
    return(
      binarySearch_onListOfNumericVectors(VecToBeQueried=VecToBeQueried,
                                          lst_ofSortedVecs=lst_ofSortedVecs,
                                          left_index = left_index, 
                                          right_index = right_index )
    )
  }
  # 4.3 If pivot_case and VecToBeQueried are identical than return pivot_index
  if(which_is_higher==3){
    return(middle_index)
  }
}