Page 111 - Computer science 868 Class 12
P. 111

3.5.3 Searching Algorithms

                 Problem 10: Write an algorithm to search any number from an array using the LINEAR SEARCH technique.



                        Note:  Linear search program is already covered in the Array chapter of this book.



                 Step 1:  Start.                                     Target                       Unsorted List
                                                                      15              13   48    7    4    15   25    11
                 Step 2:   Initialise  loop  variable  i  to  0 and  index
                         position pos to -1.                     1st Comparision

                 Step 3:  Repeat Step 4 to Step 6 while i < n.        15              13   48    7    4    15   25    11
                                                                             15≠13
                 Step 4:   If A[i]  = searchvalue  then go to Step  5,   2nd Comparision
                         else go to Step 6.
                                                                      15              13   48    7    4    15   25    11
                 Step 5:  Initialise pos to i, and go to Step 7.             15≠48
                                                                 3rd Comparision
                 Step 6:  Increment i by 1.
                                                                      15              13   48    7    4    15   25    11
                 Step 7:   If pos != -1 then go to Step 8, else go to        15≠7
                         Step 9.                                  4th Comparison
                 Step 8:   Display searchvalue “found at index” pos,   15             13   48    7    4    15   25    11
                         go to Step 10.                                      15≠4
                                                                  5th Comparison
                 Step 9:  Display searchvalue “not found”.
                                                                      15              13   48    7    4    15   25    11
                 Step 10: Stop.                                              15=15


                 Problem 11: Write an algorithm to search any number from an array using the BINARY SEARCH technique.


                        Note:  Binary search program is already covered in the Array chapter of this book.


                 This algorithm is written assuming array a[] is sorted in ascending order:

                 Step 1:  Start.
                 Step 2:   Initialise begin to 0, end to array length-1 and pos = -1.
                 Step 3:   Repeat Step 3 to Step 8 while begin <= end.
                 Step 4:  Calculate mid = (begin + end)/2.

                 Step 5:   If a[mid] = search_value then initialise                 Binary Search
                         pos = mid and go to Step 9.                        0   1    2   3    4   5   6    7   8    9

                 Step 6:   If a[mid] < search_value then initialise   Search 23  2  5  8  12  16  23  38  56   72  91
                         begin=mid+1.                                      L=0  1    2   3   M=4  5   6    7   8   H=9
                                                                23 > 16
                 Step 7:   If a[mid] > search_value then initialise   take 2  half  2  5  8  12  16  23  38  56  72  91
                                                                   nd
                         end=mid-1.                                         0   1    2   3    4  L=5  6   M=7  8   H=9
                                                                23 > 56
                 Step 8:   If pos = -1 then go to Step 10 else go   take 1  half  2  5  8  12  16  23  38  56  72  91
                                                                   st
                         to Step 11.                                                             L=5,
                                                               Found23,     0   1    2   3    4  M=5  H=6  7   8    9
                 Step 9:   Display search_value found  at index   Returns 5  2  5    8   12  16   23  38  56   72  91
                         pos, go to Step 12.


                                                                                                                       109
                                                                            Implementation of Algorithms to Solve Problems  109
   106   107   108   109   110   111   112   113   114   115   116