Page 272 - computer science (868) class 11
P. 272

28                   System.out.println(ns + " is found at index "+ pos);
                29               else

                30                   System.out.println(ns + " not found");
                31           }

                32       }

              The output of the preceding program is as follows:
              Enter the size of the array:

              4
              Enter a number: 56
              Enter a number: 32

              Enter a number: 9
              Enter a number: 45
              Enter a number to search: 9

              9 is found at index 2

              Binary Search
              In binary search, firstly, the array is arranged in ascending or descending order. Then the sorted array (in ascending
              order) is divided into two equal halves. 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
              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, the process continues in the right half. Binary
              search is also known as a half-interval search.

              Let us take the following example in which Ar is the name of the array of length 5 which is arranged in ascending order.

                              Position or index    0           1           2          3           4
                                    Ar             1           4           6          8          10
              Suppose, the number to be searched: 8
              The following steps are to be taken in the binary search technique:

              Step1:   The array is divided into two equal halves which gives the middle element 6. The number to be searched
                      is compared with the middle element and then it determines the location of the number to be searched
                      whether in the left half or right half. Accordingly, the value of variable min is assigned.
                              Position  or index   0           1           2          3           4

                                    Ar             1           4           6          8          10
                                                  Min                    Mid                     Max
                      Middle element is 6 as (0 + 4) / 2 = 2

                      Now, 8 > ar[2], i.e., 6.

                      So, it has been concluded that the element to be searched is in the right half of the array.
                      Now, min = mid + 1 = 2 + 1 = 3




                270270  Touchpad Computer Science-XI
   267   268   269   270   271   272   273   274   275   276   277