Searching in c language

Searching is an extremely fascinating and useful computer science technique. It helps to find the desired object with its location and number of occurrences. The presentation includes the basic principles, algorithms and c-language implementation.

1. Prepared By:
Dr. Chandan Kumar
Assistant Professor, Computer Science & Engineering Department
Invertis University, Bareilly

2. Introduction
In computer science, searching play a vital role
Helpful to find a desired element in a list
Also helpful to find number of occurrence of a desired
element or a place of an given element in a list

3. Searching
Anoperationorprocessortechniquetofindoutadesired
elementortheplaceofanelementinalist
Itdecideswhetheranelementispresentornot
Itisthealgorithmicmethodoffindingaparticularelement
inalist
Itcanbedoneonbothdatastructurei.e.internalor
externaldatastructure
Searchissuccessfulifthedesirednumberisfoundinalist
Searchisunsuccessfulifthedesirednumberdoesn'tfound
inalist

4. Searching Techniques
To search or find out the desired element in a list or a given
array, there are two ways-
Linear Search or Sequential Search
Binary Search or Interval Search

5. Linear or Sequential Search
Linearsearchisalsocalledsequentialsearch
Simplestmethodofsearching
Inthissearchtechnique,theitemtobefoundinthesearch
issequentiallysearchedinthelist
Sequentialsearchstartsatthestartofthelistandchecks
everyiteminthelist
Thismethodcanbeperformedonsortedorunsortedarray
orlistboth

6. Linear Search
We compare each element with the search item until the
list ends or we find it
The list given above is the list of elements in an unsorted
array. The array has seven elements. Suppose the element
to be searched is ‘16', so 16 is compared with all the
elements starting from the 0th positionelement, and the
searching process ends where 16 is found, or the list ends.

7. Linear Search
The desired number 16 has found at 6th position in an
array. so the search is successful
The performance of the linear search can be measured by
counting the comparisons done to find out an element. The
number of comparisons is O(n) i.e. time complexity of
linear search is O(n).

8. Steps to implement linear search
Step 1 -Read the search element from the user.
Step 2 -Compare the search element with the first element
in the list.
Step 3 -If both are matched, then display "Given element is
found!!!" and terminate the function
Step 4 -If both are not matched, then compare search
element with the next element in the list.
Step 5 -Repeat steps 3 and 4 until search element is
compared with last element in the list.
Step 6 -If last element in the list also doesn't match, then
display "Element is not found!!!" and terminate the
function.

9. Algorithm
Linear Search (Array A[n], Number X)
Step 1: set i to 0
Step 2: if i>n then goto step 5
Step 3: if A[i]=X then goto step 6
Step 4: set i to i+1 and goto step 2
Step 5: print element X not found and goto step 7
Step 6: print element X found at index i
Step 7: Exit

10. Implementation in C
//Linear search
#include <stdio.h>
#include<conio.h>
void main()
{
int array[100], number, i, n, count=0;
clrscr();
printf("Enter number of elements in array\n");
scanf("%d", &n);
printf("Enter %d elements \n", n);

11. for (i = 0; i < n; i++)
{
scanf("%d", &array[i]);
}
printf("Enter a desired number to search\n");
scanf("%d", &number);
for (i = 0; i < n; i++)
{
if (array[i] == number)
{
count++;
break;
}
}

12. if (count==1)
printf("%d is present at location %d.\n", number, i+1);
else
printf("%d isn't present in the array.\n", number);
getch();
}
Output:

13. Binary Search
Very fast and efficient searching technique
Used for searching an element in a sorted array only
If the array isn't sorted, we must sort it using a sorting
technique
Fast search algorithm with run-time complexity of
O(log n) wherenis total number of elements in the
list
Works on the principle of divide and conquer

14. Binary Search
This searching technique looks for a particular
element by comparing the middle most element of the
collection
Useful when there are large number of elements in an
array

15. Steps to implement Binary Search
Step 1 -Read the search element from the user.
Step 2 -Find the middle element in the sorted list.
Step 3 -Compare the search element with the middle
element in the sorted list.
Step 4 -If both are matched, then display "Given
element is found!!!" and terminate the function.
Step 5 -If both are not matched, then check whether
the search element is smaller or larger than the middle
element.

16. Steps to implement Binary Search
Step 6 -If the search element is smaller than middle
element, repeat steps 2, 3, 4 and 5 for the left sublist of
the middle element.
Step 7 -If the search element is larger than middle
element, repeat steps 2, 3, 4 and 5 for the right sublist
of the middle element.
Step 8 -Repeat the same process until we find the
search element in the list or until sublist contains only
one element.

17. Steps to implement Binary Search
Step 9 -If that element also doesn't match with the
search element, then display "Element is not found in
the list!!!" and terminate the function.

18. Algorithm
Binary Search (List,L_bound, H_bound, D_number)
Step 1: [Input] Input List, D_number
Step 2: [Initialize] set L_bound<-0, H_bound<-Sizeof(List)-1
Step 3: repeat step 4 and 5 while L_bound<=H_bound
Step 4: set mid<-(L_bound+H_bound)/2
Step 5: if List[mid]=D_number then
return mid; //Desired Number found
else if D_number<List[mid] then
H_bound<-mid -1
else
L_bound<mid+1
Step 6: print "value is not present in the array“
Step 7: Exit

19. Implementation Binary search
#include<stdio.h>
#include<conio.h>
void main()
{
int first, last, middle, size, i, sElement, list[100];
clrscr();
printf("Enter the size of the list: ");
scanf("%d",&size);
printf("Enter %d integer values in Assending order\n", size);
for (i = 0; i < size; i++)
scanf("%d",&list[i]);

20. printf("Enter value to be search: ");
scanf("%d", &sElement);
first = 0;
last = size -1;
middle = (first+last)/2;
while (first <= last)
{
if (list[middle] < sElement)
first = middle + 1;
else if (list[middle] == sElement)
{
printf("Element found at index %d.\n",middle);
break;
}

21. else
last = middle -1;
middle = (first + last)/2;
}
if (first > last)
printf("Element Not found in the list.");
getch();
}