Searching for data within a collection is a common task in computer programming, and understanding searching algorithms is essential for every programmer. In this comprehensive guide, we will explore various searching algorithms in the C programming language, providing detailed explanations, practical examples, and real data to help you master these crucial techniques.
Linear Search in C
Linear Search is the simplest searching algorithm, also known as sequential search. It checks each element of the collection until a match is found.
Example: Implementing Linear Search in C
#include <stdio.h>
int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i;
}
}
return -1; // Not found
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 22;
int result = linearSearch(arr, n, target);
if (result != -1) {
printf("Element found at index %d\n", result);
} else {
printf("Element not found\n");
}
return 0;
}Output:
Element found at index 4
In this example, we implement Linear Search to find a target element in an array of integers.
Binary Search in C
Binary Search is a more efficient searching algorithm, but it requires the input collection to be sorted. It repeatedly divides the collection in half and narrows down the search space.
Example: Implementing Binary Search in C
#include <stdio.h>
int binarySearch(int arr[], int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // Not found
}
int main() {
int arr[] = {11, 12, 22, 25, 34, 64, 90};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 22;
int result = binarySearch(arr, 0, n - 1, target);
if (result != -1) {
printf("Element found at index %d\n", result);
} else {
printf("Element not found\n");
}
return 0;
}Output:
Element found at index 2
In this example, we implement Binary Search to find a target element in a sorted array of integers.
