Philnits sure is useful. The review reminded me of Searching 101 from which I only remember the Linear Search algorithm. Linear search is a method of searching in sequential order. Given the following values:
A = {4, 20, 31, 50, 23, 11, 30}
index 1 2 3 4 5 6 7
Searching is performed in sequential order which means if we are looking for the number 50, we start comparing it from values of index 1 until we reach the search item.
Another sorting algorithm is the Binary Search which is very useful when the elements are already sorted. Given the following values:
A = {1, 12, 30, 34 ,50 ,56, 67, 78, 89}
index 1 2 3 4 5 6 7 8 9
We would like to look for the number 67,
We first get the median value:
M = (1+9)/2 = 5
A[5] = 50
We disregard the lower half because 50<67.
The lower bound now becomes M+1.
L = M+1 = 5 +1 = 6
The new median now becomes M = (Lower bound + Upper bound)/2
M = (6 + 9) / 2 = 7.5
We round this off so it becomes 8.
A[8] = 78
78>67 so we disregard the upper half.
Since we disregarded the upper half, the new search range would now be from index 6 up to 8. Unlike earlier where we disregarded the lower part, we immediately took the value to the right of the median as the lower bound (L = M+1). This time however, since we disregarded the upper bound, we now get the upper bound instead of the lower bound: U = M-1.
U = 8-1 = 7
Since we already finished comparing with the lower bound 6, and there is no other index to compare, we compare with the upper bound 7.
A[7] = 67?
A[7] = 67 = 67
We now have the answer.
A = {4, 20, 31, 50, 23, 11, 30}
index 1 2 3 4 5 6 7
Searching is performed in sequential order which means if we are looking for the number 50, we start comparing it from values of index 1 until we reach the search item.
Another sorting algorithm is the Binary Search which is very useful when the elements are already sorted. Given the following values:
A = {1, 12, 30, 34 ,50 ,56, 67, 78, 89}
index 1 2 3 4 5 6 7 8 9
We would like to look for the number 67,
We first get the median value:
M = (1+9)/2 = 5
A[5] = 50
We disregard the lower half because 50<67.
The lower bound now becomes M+1.
L = M+1 = 5 +1 = 6
The new median now becomes M = (Lower bound + Upper bound)/2
M = (6 + 9) / 2 = 7.5
We round this off so it becomes 8.
A[8] = 78
78>67 so we disregard the upper half.
Since we disregarded the upper half, the new search range would now be from index 6 up to 8. Unlike earlier where we disregarded the lower part, we immediately took the value to the right of the median as the lower bound (L = M+1). This time however, since we disregarded the upper bound, we now get the upper bound instead of the lower bound: U = M-1.
U = 8-1 = 7
Since we already finished comparing with the lower bound 6, and there is no other index to compare, we compare with the upper bound 7.
A[7] = 67?
A[7] = 67 = 67
We now have the answer.
Comments