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

