Linear and Binary Searches
Linear Search:


Binary Search:


binary search 
A technique for finding an element in a sorted list by dividing 
the list in two and deciding which half the sought after 
element lives in, then dividing the list in two again, 
gradually narrowing down the possible location of the sought after 
element. Its advantage is that it takes no extra RAM. It is faster 
than ArrayList.contains which simply compares every element in 
the collection. Binary search requires log2 n compares vs n/2 
compares for a linear search. You invoke it with: 
boolean found = Arrays.binarySearch ( stringArray, stringToSearchFor ) >= 0;

binarySearch tells you where it found the match, and if it does not 
find a match, it tells you where the match would have been. binarySearch 
also has a variant that takes a Comparator to define a custom 
ordering. The elements must be in order by that Comparator. 
Collections.binarySearch works on List collections.



Binary Search tree is a binary tree in which each internal node x 
stores an element such that the element stored in the left subtree 
of x are less than or equal to x and elements stored in the right 
subtree of x are greater than or equal to x. This is called 
binary-search-tree property. 
The basic operations on a binary search tree take time proportional 
to the height of the tree. For a complete binary tree with node n, 
such operations runs in (lg n) worst-case time. If the tree is a 
linear chain of n nodes, however, the same operations takes (n) 
worst-case time.

The height of the Binary Search Tree equals the number of links 
from the root node to the deepest node.

Best-case running time 
Printing takes O(n) time and n insertion cost O(lg n)
each (tree is balanced, half the insertions are at depth lg(n) -1). 
This gives the best-case running time O(n lg n). 
  
Worst-case running time 
Printing still takes O(n) time and n insertion 
costing O(n) each (tree is a single chain of nodes) 
is O(n2). The n insertion cost 1, 2, 3, . . . n, 
which is arithmetic sequence so it is n2/2. 

So basically, it takes a list, splits it in half, if the object
isn't in the first half, it looks at the second half, then, it
splits that half into a second half and looks for it again, 
splitting it until the object is located.




https://www.angelfire.com/mech/kaelinmulcahy/code



https://www.angelfire.com/mech/kaelinmulcahy/sitesused