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.

0 Responses to "A review on Searching Algorithms"Post a Comment