binarySearch_onListOfNumericVectors: Perform binary search on list of numeric vectors using query...

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

Description

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.

Usage

binarySearch_onListOfNumericVectors(
  VecToBeQueried,
  lst_ofSortedVecs,
  left_index = 1,
  right_index = length(lst_ofSortedVecs),
  verbose = F
)

Arguments

VecToBeQueried	Numeric vector to be queried
lst_ofSortedVecs	List of numeric vectors sorted by values in increasing order

Details

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.

Value

A numeric key index of lst_ofSortedVecs corresponding to query. NA is returned if VecToBeQueried is not in lst_ofSortedVecs.

msxakk89/dat documentation built on Aug. 3, 2020, 6:39 p.m.