What is Searching? Define its Type and Characteristics. Also write a C Program for Linear Search and Binary Search.
Searching
Searching is the
process of finding a specific element in a collection of data. It is a
fundamental problem in computer science and is used in many applications,
including information retrieval, database management, and artificial
intelligence.
There are various types
of searching algorithms, including:
1. Linear Searching
2. Binary Searching
1. Linear search: It is a simple searching algorithm that checks each
element in the collection until the target element is found or the entire
collection is checked.
2. Binary search: It is a more efficient
searching algorithm that works by repeatedly dividing the collection in half
and checking whether the target element is in the first or second half.
Characteristics of Linear Search:
o Linear search is a
simple and easy-to-understand algorithm that is appropriate for small
collections.
o Linear search has a
time complexity of O(n) in the worst and average cases, where n is the number
of elements in the collection.
o Linear search is an
example of a brute force algorithm because it checks every element in the
collection.
//C Program to Search Element using Linear Search.
#include <stdio.h>
int main()
{
int array[100], search, c, n;
printf("Enter number of elements in array\n");
scanf("%d", &n);
printf("Enter %d integer(s)\n", n);
for (c = 0; c < n; c++)
scanf("%d", &array[c]);
printf("Enter a number to search\n");
scanf("%d", &search);
for (c = 0; c < n; c++)
{
if (array[c] == search) /* If
required element is found */
{
printf("%d is present at location %d.\n", search, c+1);
break;
}
}
if (c == n)
printf("%d isn't present in the array.\n", search);
return 0;
}
Characteristics of Binary Search:
o Binary search is a more
efficient algorithm than linear search, especially for large collections.
o Binary search requires
the collection to be sorted beforehand, which can take additional time.
o Binary search has a
time complexity of O(log n) in the worst and average cases, where n is the
number of elements in the collection.
o Binary search works by
dividing the collection in half at each step, which reduces the number of
elements to be searched by half, resulting in faster search times.
o Binary search is a
divide-and-conquer algorithm that breaks the problem into smaller subproblems
and combines the results.
#include <stdio.h>
int binarySearch(int array[], int x,
int low, int high) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (array[mid] == x)
return mid;
if (array[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
int main(void) {
int array[] = {3, 4, 5, 6, 7, 8, 9};
int n = sizeof(array) / sizeof(array[0]);
int x = 4;
int result = binarySearch(array, x, 0, n - 1);
if (result == -1)
printf("Not found");
else
printf("Element is found at index %d", result);
return 0;
}
In summary, linear
search is a simple and straightforward algorithm that is suitable for small
collections, while binary search is a more efficient algorithm that requires
the collection to be sorted beforehand but can handle larger collections with
faster search times.
Comments
Post a Comment