- Linear Search
- Binary Search
LINEAR SEARCH:
Suppose DATASET we use for an algorithm is a linear sequence with n elements. No other information about DATASET is available, the most spontaneous(naive “pronounced as na-ive”) and brute force approach order to search for a given VALUE in DATASET is to compare VALUE with each element of DATASET one by one. First, we need to test whether DATASET[1]=VALUE, and then we test whether DATASET[2] =VALUE and so on. This method which traverses DATA sequentially to locate ITEM is called linear search or sequential search.
Algorithm :
LINEAR (DATA, N, ITEM, LOC)
Step 1: [Insert ITEM at the end of data]
Set DATA [N+1] = ITEM
Step 2: [Initialize counter]
Set LOC=1
Step 3: [Search for ITEM]
Repeat while DATA [LOC]!= ITEM
Step 4: [Successful]
If LOC=N+1
Then Set LOC = 0
Step 5: Exit
The complexity of Linear Search Algorithm: The complexity of this search algorithm is measured by the number of functions f(n) of comparisons required to find VALUE in DATASET where DATASET contains n elements.
There are two important cases to consider: the average case and the worst cases.
The worst-case occurs when one may search through the entire sequence of DATASET. In this case, the algorithm requires F(n)= n+1 comparisons. Thus, it is justified that in the worst case, running time is proportional to n(size of sequence).
The average case running time uses the probabilistic notion of expectation. The probability that VALUE appears in DATASET[K] and q is the probability that VALUE does not appear in DATASET. Since the algorithm uses k comparisons when VALUE appears in DATASET[K], the average number of comparisons is given by F(n) = 1. p1 + 2. p2 +…..+ n.pn + (n+1).q.
BINARY SEARCH:
Suppose DATASET is an array that is sorted in increasing numerical order. Then there is an extremely efficient searching algorithm, called binary search.
Algorithm :
Binary search (DATA, LB, UB, ITEM, LOC)
Step 1: [Initialize the segment variables]
Set BEG := LB, END := UB and MID := INT ((BEG + END)/2)
Step 2: [Loop]
Repeat Step 3 and Step 4 while BEG <= END and DATA [MID] != ITEM
Step 3: [Compare]
If ITEM < DATA [MID]
then set END := MID - 1
Else
Set BEG = MID + 1
Step 4: [Calculate MID]
Set MID := INT ((BEG + END)/2)
Step 5: [Successful search]
If DATA [MID] = ITEM
then set LOC := MID
Else set LOC := NULL
Step 6: Exit
The time complexity of the Binary Search Algorithm: The complexity is measured by the number of functions f(n) of comparison to locate VALUE in DATASET where DATASET contains n elements. Observe that each comparison reduces the sample size in half of its size in the past. Hence we require at most f(n) comparisons to locate VALUE where 2f(n) > n Or equivalently F(n) = [log2 n] + 1.
The running time for the worst case is approximately equal to log2 n and the average case is approximately equal to the running time for the worst case.
0 Comments
Doubts? Please let our team know So that we can serve you better.