Binary and Ternary Search Algorithm by R

Pseudocode

binary search

function search(list, target)

          var left = 1, right = list.length

          while left <= right

                   var middle = get the middle point of the list

                   if list[middle] == target

                             return middle

                   // if it’s greater than target, search the left-hand half side

                   else if list[middle] > target

                             right = middle - 1

                   // if it’s smaller than target, search the right-hand half side

                   else if list[middle] < target

                             left = middle + 1

                   end if

          end while

          return -1

end function

ternary search

function search(list, target)

          var left = 1, right = list.length

          while left <= right

                   var middle1 = get the first middle point of the list

                   var middle2 = get the second middle point of the list

                   if list[middle1] == target

                             return middle1

                   if list[middle2] == target

                             return middle2

                   // if middle1 is greater than target, search between left and middle1

                   else if list[middle1] > target

                             right = middle1 - 1

                   // if middle2 is smaller than target, search between middle2 and right

                   else if list[middle2] < target

                             left = middle2 + 1

                   // else: search between middle1 and middle2

                   else

                             left = middle1 + 1

                             right = middle2 -1

                   end if

          end while

          return -1

end function

Equation

binary search

time spent for binary = 0.0453684210526345 + 6.18345864661649e-06 * number of elements

ternary search

time spent for ternary = 0.0715789473684291 + 6.39849624060138e-06 * number of elements

Empirical Graph

Original R Code

https://drive.google.com/file/d/1WQ6VFtvmGo19UGJ9uYZilwBDxxmdNhJb/view?usp=sharing