Searching
There are many different searching algorithms. We are discussing two very common search techniques viz. linear search and binary search.
Linear Search
In linear search,each element of the array is compared with the given Item to be searched for, one by one. This method, which traverses the array sequentially to locate the given Item, is called linear search or sequential search.
LINEAR SEARCH IN ARRAY
/* Initialise counter by assigning lower bound value of the array */
Step 1. Set ctr = L // In C++, L (Lower bound) is 0 (zero)
/* Now search for the ITEM */
Step 2. Repeat steps 3 through 4 until ctr > U. // In C++ U (Upper bound) is size-1
Step 3. IF AR[ctr] = = ITEM then
{
print "search Successful"
print ctr, "is the location of", ITEM
break /* go out of loop */
}
Step 4. ctr = ctr + 1
/* End of Repeat */
Step 5. IF ctr > U then
print "Search Unsuccessful !"
Step 6. END
The above algorithm searches for ITEM in array AR with lower bound L and upper bound u. As soon as the search is successful, it jumps out of the loop (break statement) otherwise continues till the last element.
Binary Search
This popular search technique searches the given ITEM in minimum possible comparisons. The binary search requires the array, to be scanned, must be sorted in any order (for instance, say ascending order). In binary search, the ITEM is searched for in smaller segment (nearly half the previous segment) after every stage. For the first stage, the segment contains the entire array.
To search for ITEM in a sorted array (in ascending order), the ITEM is compared with middle element of the segment (i.e, in the entire array for the first time). IF the ITEM is more than the middle element, latter part of the segment becomes new segment to be scanned; if the ITEM is less than the middle element, former part of the segment becomes new segment to be scanned. The same process is repeated for the new segment(s) until either the ITEM is found (search successful) or the segment is reduced to the single element and still the ITEM is not found (search unsuccessful).
BINARY SEARCH IN ARRAY
Case I : Array AR [L : U] is stored in ascending order
/* Initialise segment variables */
1. Set beg = L, last = U // In C++, L is 0 and U is size-1.
2. REPEAT steps 3 through 6 UNTIL beg > last // INT ( ) is used to extract integer part
3. mid = INT ( (beg + last)/2)
4. if AR [mid] == ITEM then
{
print "search Successful"
print ITEM, "found at",mid
break /* go out of the loop */
}
5. if AR[mid] < ITEM then
beg = mid + 1
6. if AR[mid] > ITEM then
last = mid - 1
/* End of repeat */
7. if beg ≠last
print "Unsuccessful Search"
8. END
Case II : Array AR [L : U] is stored in descending order
/* Initialise */
:
if AR[mid] = = ITEM then
{ :
}
if AR[mid] < ITEM then
last = mid -1
if AR [mid] > ITEM then
beg = mid + 1
:
// Rest is similar to the algorithm in case I.
Linear Search
In linear search,each element of the array is compared with the given Item to be searched for, one by one. This method, which traverses the array sequentially to locate the given Item, is called linear search or sequential search.
LINEAR SEARCH IN ARRAY
/* Initialise counter by assigning lower bound value of the array */
Step 1. Set ctr = L // In C++, L (Lower bound) is 0 (zero)
/* Now search for the ITEM */
Step 2. Repeat steps 3 through 4 until ctr > U. // In C++ U (Upper bound) is size-1
Step 3. IF AR[ctr] = = ITEM then
{
print "search Successful"
print ctr, "is the location of", ITEM
break /* go out of loop */
}
Step 4. ctr = ctr + 1
/* End of Repeat */
Step 5. IF ctr > U then
print "Search Unsuccessful !"
Step 6. END
The above algorithm searches for ITEM in array AR with lower bound L and upper bound u. As soon as the search is successful, it jumps out of the loop (break statement) otherwise continues till the last element.
Binary Search
This popular search technique searches the given ITEM in minimum possible comparisons. The binary search requires the array, to be scanned, must be sorted in any order (for instance, say ascending order). In binary search, the ITEM is searched for in smaller segment (nearly half the previous segment) after every stage. For the first stage, the segment contains the entire array.
To search for ITEM in a sorted array (in ascending order), the ITEM is compared with middle element of the segment (i.e, in the entire array for the first time). IF the ITEM is more than the middle element, latter part of the segment becomes new segment to be scanned; if the ITEM is less than the middle element, former part of the segment becomes new segment to be scanned. The same process is repeated for the new segment(s) until either the ITEM is found (search successful) or the segment is reduced to the single element and still the ITEM is not found (search unsuccessful).
BINARY SEARCH IN ARRAY
Case I : Array AR [L : U] is stored in ascending order
/* Initialise segment variables */
1. Set beg = L, last = U // In C++, L is 0 and U is size-1.
2. REPEAT steps 3 through 6 UNTIL beg > last // INT ( ) is used to extract integer part
3. mid = INT ( (beg + last)/2)
4. if AR [mid] == ITEM then
{
print "search Successful"
print ITEM, "found at",mid
break /* go out of the loop */
}
5. if AR[mid] < ITEM then
beg = mid + 1
6. if AR[mid] > ITEM then
last = mid - 1
/* End of repeat */
7. if beg ≠last
print "Unsuccessful Search"
8. END
Case II : Array AR [L : U] is stored in descending order
/* Initialise */
:
if AR[mid] = = ITEM then
{ :
}
if AR[mid] < ITEM then
last = mid -1
if AR [mid] > ITEM then
beg = mid + 1
:
// Rest is similar to the algorithm in case I.
No comments