Page 373 - CA_Blue( J )_Class10
P. 373

Linear Search
                 Linear search is the simplest technique of searching. In this technique, the searching of an item will begin from the 0th
                 position of the array and will traverse till the end. If the element is found, the searching will stop, else will continue till
                 the last and then stop.
                 Let us take an example, in which the number to be searched is 14:
                                              index     0       1       2       3       4
                                                ar      10      21      24      14      11

                 Step 1:  ar[0] i.e  10    ==    14 : false

                 Step 2:  ar[1] i.e. 21   ==    14 : false
                 Step 3:  ar[2] i.e. 24   ==   14 : false
                 Step 4:  ar[3] i.e. 14   ==   14 : true : break from loop

                 This process of searching is also known as sequential searching as it searches an item in an array in a sequential
                 manner either top to bottom or vice versa. The element to be searched is mapped with each element of the array.
                 When the element is matched, searching stops.


                 Binary Search
                 In this technique, an array has to be arranged in ascending or descending order. The sorted array (in ascending order)
                 has to be divided into two equal halves. Then the element to be searched is checked with the middle element. If
                 it matches, then the loop breaks, else it checks whether the searched element is larger or smaller than the middle
                 element. If it is a smaller than the middle element, then the left side is again divided into two halves and the process
                 continues. Similarly, if the searched element is larger than the middle element, in the right half the process continues.
                 Binary search is also known as half-interval search.

                 Let us take an example, in which the element to be searched is 44:
                                              index     0       1       2       3       4
                                                ar      10      21      24      44      51

                 Step1:

                                              index     0       1       2       3       4
                                                ar      10      21      24      44      51
                                                       min             mid             max
                                                                                                      nd
                 Middle element of the array is = (First Index + Last Index)/2 = (0 + 4)/2 = 2. The element of the 2  position will be the
                 middle element of the array which 24.
                 Now, check whether the element to be searched 44 is greater than middle element of the array 24. If it is true, then it
                 has been concluded that the element to be searched is in the right half of the array. If it is false, then the element to
                 be searched is in the left half of the array.
                 Step 2:  Again, find the middle element of the right half of the array.

                                              index     0       1       2       3       4
                                                ar      10      21      24      44      51
                                                                               min     max
                                                                               mid
                 Middle element is 44 as (3+4)/2 = 7/2 = 3 (taking only the integer part)





                                                                                                                       371
                                                                                                              Arrays   371
   368   369   370   371   372   373   374   375   376   377   378