Page 296 - Cs_withBlue_J_C11_Flipbook
P. 296
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
294294 Touchpad Computer Science-XI

