There are many different techniques or algorithms for searching and sorting.
The linear search is an O(N) "linear" complexity. We will look at another searching algorithm, the binary search below.
For selection sorting we determined that the complexity is O(N2).
There are sorters that are variations on O(N2), but still have
the property of quadrupling the time when the size of the vector is doubled.
There are sorting algorithms that are O(N log N) which are better.
Part of searching a vector is tracking the range of elements yet to be searched. Consider the linear search. The range is from the index to the end of the array. For the binary search we keep two indexes into the vector, a low and high. Either end can be adjusted.
The binary search is a form of the high-low game.
while the element is not found and may still be in the vector{
determine the position of the middle element
if the middle element isn't the search key
reset one of the indexes to halve the range of possibilities
void BinSearch ( /*in */ const vector ElemType & vec,
/*in */ int n,
/*in */ ElemType key,
/*out*/ int & loc)
{
int lo = 0;
int hi = n-1;
loc = hi / 2;
while (lo <= hi && vec[loc] != key) {
if (key > vec[loc]){
lo = loc+1;
} else {
hi = loc-1;
}
loc = (lo + hi)/2;
}
}
Enter a search key for the array below and follow the Low, High and
Mid indexes through the binary search.