# Searching

There are many different searching algorithms. We are discussing two very common search techniques viz. linear search and binary 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.

/* 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.

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).

/* 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

/* 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