Search Algorithms

Two popular search algorithms are linear and binary search.
Linear search algorithm searches each item sequentially to see if the search key is present.

Efficiency of search algorithm

The major thing that differentiate search algorithms is the amount of effort required to complete
the search. This is described by Big 0 notation. How hard an algorithm has to work to solve a
problem.
If the algorithm is independent of the number of elements in the array it is said to have a
constant run time 0(1) this means the number of comparisons are constant - it does not grow
when the size of the array increases.
An algorithm that test whether the first element is equal to any other element in the array will
require n-1 comparisons is 0(n) algorithm having a linear run time pronounced on the order of n
or order n.

Now suppose an algorithm has to test whether any element is duplicated anywhere in the
array. Big 0 is concerned with how an algorithms run time grows in relation to how many items
it processes. Suppose an algorithm requires n² comparisons. The algorithm is considered to
be 0(n²) referred to as a quadratic run time pronounced on the order of n squared or order
n squared. As n grows you will start to notice performance degradation. The linear search
algorithm can provide great performance if the search element is at or near the front of the
array.

Binary search

This is more efficient than linear search but requires the elements to be sorted first. The
first iteration tests the middle element in the array. If the search key matches the element
the algorithm ends. Assuming the array is sorted, if the search key is less than the middle
element it cannot be in the second half. The algorithm continues with only the first half of the
array. Each iteration tests the middle half of the remaining array if the element does not match,
the algorithm eliminates half again until it finds a match or reduces the sub array to zero.

Efficiency of a binary search

In the worst case scenario searching a sorted array of 1023 elements will require at most 10

comparisons in a binary search. The number 1023 (2¹⁰ -1) is divided by 2 only 10 times to get

to the value 0. Dividing by 2 is equivalent to one comparison in a binary search. An array of

over one billion elements takes a maximum of 30 comparisons to find the key. A tremendous

improvement on performance over a linear search. The maximum comparison required by a

binary search of a sorted array is the exponent of the first power of 2 greater than the number

of elements in the array which is represented as log₂n . Logarithms grow at roughly the same

rate. This results in a big 0 notation of 0(log n) for a binary search or logarithmic run time.