Table of Contents
show
To find whether a given number is present in an array and if it is present then at what location it occurs.Â
Types of Searching
- Linear Search
- Binary Search
Linear Search
In Linear Search the list is searched sequentially and the position is returned if the key element to be searched is available in the list, otherwise -1 is returned. The search in Linear Search starts at the beginning of an array and move to the end, testing for a match at each item.
Program: Implementation of Linear search
#include <stdio.h>
int main()
{
int array[100], value, i, n,pos = -1;
printf("Enter the number of elements in array\n");
scanf("%d",&n);
printf("Enter numbers \n");
for (i = 0; i < n; i++)
{
scanf("%d", &array[i]);
}
printf("Enter the number to search\n");
scanf("%d", &value);
for (i = 0; i< n; i++)
{
if (array[i] == value) /* if required element found */
{
pos = i;
break;
}
}
if (pos != -1)
{
printf("%d is present at array index %d.\n", value, pos);
}
else
{
printf("%d is not present in array.\n", value);
}
return 0;
}Output
Enter the number of elements in array
5
Enter numbers
4 5 3 9 1
Enter the number to search
3
3 is present at array index 2.Binary Search
It can only be used for sorted arrays, but it’s fast as compared to linear search. It compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful.
Program: Implementation of Binary Search
#include <stdio.h>
int main()
{
int c, first, last, middle, n, search, array[100];
printf("Enter number of elements\n");
scanf("%d",&n);
printf("Enter %d integers\n", n);
for (c = 0; c < n; c++)
{
scanf("%d",&array[c]);
}
printf("Enter value to find\n");
scanf("%d", &search);
first = 0;
last = n - 1;
middle = (first+last)/2;
while (first <= last)
{
if (array[middle] < search)
{
first = middle + 1;
}
else if (array[middle] == search)
{
printf("%d found at array index %d.\n", search, middle);
break;
}
else
{
last = middle - 1;
}
middle = (first + last)/2;
}
if (first > last)
{
printf("Not found! %d is not present in the list.\n", search);
}
return 0;
}Output
Enter number of elements
5
Enter 5 integers
6 7 8 9 10
Enter value to find
9
9 found at array index 3.Views: 0