Why?:
One commonly used algorithm is the binary search.
If you don't already know it, you should read on.
Very helpful. Saves much CPU. Reduces computations exponentially.
When searching though a lot of information to find a match, the first idea that comes to mind is the linear search. Loop through all the values looking for a match. If you find it, return the location, or value and end the search.
However this becomes highly inefficient when the values to be searched become very large. It's a O(N) algorithm. At worse case you may have to search ALL the values to find a match, or even worse find that it's not there!
How?:
If the list of items can be sorted numerically or ASCII. Use a binary search!
First, sort the list.Then compare the value in the very center (round up or down in case of uneven list elements) to your search term. If it is "less than" your term, you know that it must be
lower than that point. So you can eliminate the upper range. If the term has a greater value than your center point value, eliminate the lower range.
Thus reducing the amount of items to be searched by half.
Apply this technique to the remaining items continually and reduce the search by half each iteration.
Thus running at the much faster O(log N) algorithm.
Example: Warning: uses "recursion", remember to consider function call loads on CPU. In some languages this can actually be slower than linear. See non recursive below.
(taken from
Wikipedia)
-
BinarySearch(A[0..N-1], value, low, high) {
-
if (high < low)
-
return -1 // not found
-
mid = low + ((high - low) / 2) // Note: not (low + high) / 2 !!
-
if (A[mid] > value)
-
return BinarySearch(A, value, low, mid-1)
-
else if (A[mid] < value)
-
return BinarySearch(A, value, mid+1, high)
-
else
-
return mid // found
-
}
-
There is an optimization here.
Sometimes when dealing with large numbers, or floating point high precision.
mid = (low + high)/2
can overflow and hog memory, resulting in unreliable results.
mid = low + ((high - low)/2)
fixes it. :)
See here... Non Recursive: -
low = 0
-
high = N
-
while (low < high) {
-
mid = low + ((high - low) / 2) // Note: not (low + high) / 2 !!
-
if (A[mid] < value)
-
low = mid + 1;
-
else
-
//can't be high = mid-1: here A[mid] >= value,
-
//so high can't be < mid if A[mid] == value
-
high = mid;
-
}
-
// high == low, using high or low depends on taste
-
if ((low < N) && (A[low] == value))
-
return low // found
-
else
-
return -1 // not found
-
There are MANY sources for this most elementary algorithm. Just type "binary search" into Google.
Happy coding....
