SEARCHING : We know the general meaning of concept is finding any thing. Here in data structure we use concept of searching for finding data from any list.For this purpose there are so many type of searching algorithm are used.
Basically there are three type of Search :
👉 Linear Search or Sequential Search
👉 Binary Search.
👉 Interpolation Search.
LINEAR SEARCH: In linear search method starting from first element of list. We compare each and every element of list with a search element (S), If found , we return position as a positive result , If not found , we return (-1) as a negative result.
Example:
If a[0]==S FALSE [ If true return 0 ]
If a[1]==S FALSE [ If true return 0 ]
If a[2]==S TRUE return 2 ]
ALGORITHM FOR LINEAR OR SEQUENTIAL SEARCH:
A IS AN ARRAY WITH N - ELEMENT
STEP 1: FOR I=0 TO N-1 DO
STEP 2: IF A[I] ==S
STEP 2.1: RETURN I
STEP 3: END IF
STEP 4:NEXT I
STEP 5: RETURN (-1)
STEP 6: END
PROCEDURE OF LINEAR OR SEQUENTIAL SEARCH IN C
int seqsearch ( int a[10], int s)
{
int i;
for ( i=0; i<n ; i++ )
{
if ( a[i] ==s )
{
return (i);
}
}
return (-1);
}
EVALUATION OF SEQUENTIAL SEARCH:
BEST CASE : Best case for sequential search occur when element is found in first attempts.In such case sequential search need one comparison with complexity O(1).
WORST CASE : Worst case for sequential search occur when search element is not available in array. In such case sequential search needs n comparisons with complexity O(n).
BINARY SEARCH: Binary Search method is based on divide & concur strategy. In Binary search first we compare mid position element of array with (S). If found we return (mid) as a result But if not we compare (mid) position element with (S) such that If mid position element is greater then (S) then we discard second part and continue binary search with first part (low to mid-1).
If mid position is less than (S) then we discard Ist part (low to mid-1) and continue binary search with 2nd part (mid+1 to high).
We proceed above method until array has a single element.
In the above method we assume that array is already sorted in ascending order.
Example:
a[mid] ==S FALSE ( If TRUE return (MID))
a[mid] > S FALSE (If TRUE Ist part [low,mid-1])
a[mid] < S TRUE ( IInd Part ( mid+1, high))
ALGORITHM FOR BINARY SEARCH (RECURSIVELY):
A IS AN ARRAY WITH N ELEMENT
STEP 1: IF (LOW <= HIGH)
STEP 2: MID = 9 LOW + HIGH)/2
STEP 3; IF (A[MID] == S)
STEP 4: RETURN (MID)
STEP 5; ELSE
STEP 6: IF (A[MID]>S)
STEP 7; RECURSIVELY CALL , BSEARCH (A, LOW, MID-1, S)
STEP 8: ELSE
STEP 9: RECURSIVELY CALL , BSEARCH ( A, MID+1, HIGH, S )
STEP 10: END IF
STEP 11: END IF
STEP 12 : RETURN (-1)
STEP 13: END
PROCEDURE FOR BINARY SEARCH (RECURSIVELY):
int BSearch ( int a[50], int low, int high, int S )
{
int mid;
if (low <= high)
{
mid= (low + high)/2;
if (a[mid] == S )
{
return (mid);
}
else
{
if (a[mid] >S )
{
BSearch (a, low, mid-1, S);
}
else
{
BSearch (a, mid+1, high, S );
}
}
}
return (-1);
}
EVALUATION OF BINARY SEARCH:
BEST CASE: Best case for binary search occur when element is found in first attempt. In such case it needs just one comparison with complexity bigo of 1 [O(1)].
WORST CASE : Worst case for binary search occur when search element is not in array. In such case for an array of (n) element binary search need at most (log n) comparisons with complexity O(log2n).
ADVANTAGE AND DISADVANTAGE OF BINARY AND SEQUENTIAL SEARCH:
ADVANTAGE OF SEQUENTIAL SEARCH:
👉 It can be applicable in any type of storage structure.
Note : There are two type of storage structure:
1. Sequential structure storage device (ex: link list, Tape device)
2. DASD : Direct access storage device.
👉 It can perform on unsorted structure.
DISADVANTAGE OF BINARY SEARCH:
👉 It can perform direct access storage device. Ex: arrays.
👉 It can applicable in only sorted elements.
ADVANTAGE OF BINARY SEARCH :
👉 It is very fast method & take very less time.
No comments:
Post a Comment