Binary Search on Arrays and Linked Lists

Part 1 

Binary search trees are types of containers in data structures that store items like names or numbers in memory. They are used to facilitate a fast lookup or search to remove or add items in an array by using their keys. The keys are sorted in order so that the binary search can be applied from left to right or from bottom to top. The searching allows for comparison that is equivalent to half of the number of items in an array. This property makes binary search tree quicker and better than linear search. Each search, deletion or lookup takes the time that is directly proportional to the elements stored in the array ( Lafore, 2017) . Array elements are stored form index 0 onwards. The first character of the array is at a position called index 0. An element at index 4 has four characters before it. In an array of n elements, the minimum index is 0, and the maximum index is n-1. A guess is calculated on the average of minimum and maximum. The value is rounded down to obtain a whole number. If the array guess is equivalent to the target element, then the binary search stops. If the guess is lower than the target, then the guess is set at plus 1. If the guess is higher than the target, then it is set at minus 1. The process is repeated until the target element is found. 

A linked list has a single next reference while a binary tree has two next references. During a binary search, the linked list has a longer path or number elements to travel through than a binary tree ( Michu, DELHI, Michu, & DELHI, 2018) . Elements are stored in nodes, and each node keeps track of its immediate child element. Each node points to the left and right child nodes using the binary tree. If there is no left or right child, the pointer is equivalent to NULL. A pointer is required to point to the root of the tree to keep track of all the elements in the tee.