Recent Post

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.      

No comments