Searching is the process of finding the location of a specific element in a data structure. In C, various searching techniques are used, depending on the type of data structure and requirements.
1. Linear Search
Linear search is a basic technique where each element is checked sequentially until the target is found or the list ends.
Characteristics:
- Works for both sorted and unsorted data.
- Time Complexity: O(n)O(n)O(n)
- Space Complexity: O(1)O(1)O(1)
C Code Example:
#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 the index of the target element
}
}
return -1; // Element not found
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 30;
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;
}
2. Binary Search
Binary search is an efficient algorithm for sorted arrays. It repeatedly divides the search interval in half until the target is found.
Characteristics:
- Requires the array to be sorted.
- Time Complexity: O(logn)O(\log n)O(logn)
- Space Complexity: O(1)O(1)O(1) (iterative) or O(logn)O(\log n)O(logn) (recursive).
Iterative C Code Example:
#include <stdio.h>
int binarySearch(int arr[], int n, int target) {
int left = 0, right = n – 1;
while (left <= right) {
int mid = left + (right – left) / 2;
if (arr[mid] == target) {
return mid; // Element found
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid – 1;
}
}
return -1; // Element not found
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 30;
int result = binarySearch(arr, n, target);
if (result != -1) {
printf(“Element found at index %d\n”, result);
} else {
printf(“Element not found\n”);
}
return 0;
}
3. Jump Search
Jump Search works for sorted arrays and skips some elements to reduce comparisons. It uses a fixed jump size (n\sqrt{n}n).
Characteristics:
- Requires sorted data.
- Time Complexity: O(n)O(\sqrt{n})O(n)
- Space Complexity: O(1)O(1)O(1)
C Code Example:
#include <stdio.h>
#include <math.h>
int jumpSearch(int arr[], int n, int target) {
int step = sqrt(n);
int prev = 0;
while (arr[step – 1] < target && step < n) {
prev = step;
step += sqrt(n);
}
for (int i = prev; i < step && i < n; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
int main() {
int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 40;
int result = jumpSearch(arr, n, target);
if (result != -1) {
printf(“Element found at index %d\n”, result);
} else {
printf(“Element not found\n”);
}
return 0;
}
4. Interpolation Search
Interpolation search is an improvement over binary search for uniformly distributed data. It calculates the probable position of the target element using interpolation.
Characteristics:
- Requires sorted and uniformly distributed data.
- Time Complexity: O(loglogn)O(\log \log n)O(loglogn) (best case), O(n)O(n)O(n) (worst case).
- Space Complexity: O(1)O(1)O(1)
C Code Example:
#include <stdio.h>
int interpolationSearch(int arr[], int n, int target) {
int low = 0, high = n – 1;
while (low <= high && target >= arr[low] && target <= arr[high]) {
int pos = low + ((double)(high – low) / (arr[high] – arr[low])) * (target – arr[low]);
if (arr[pos] == target) {
return pos;
} else if (arr[pos] < target) {
low = pos + 1;
} else {
high = pos – 1;
}
}
return -1; // Element not found
}
int main() {
int arr[] = {10, 20, 30, 40, 50, 60, 70};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 40;
int result = interpolationSearch(arr, n, target);
if (result != -1) {
printf(“Element found at index %d\n”, result);
} else {
printf(“Element not found\n”);
}
return 0;
}
5. Exponential Search
Exponential Search is used for sorted arrays. It finds the range for the binary search by repeatedly doubling the step size.
Characteristics:
- Requires sorted data.
- Time Complexity: O(logn)O(\log n)O(logn)
- Space Complexity: O(logn)O(\log n)O(logn) (recursive) or O(1)O(1)O(1) (iterative).
C Code Example:
#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;
}
int exponentialSearch(int arr[], int n, int target) {
if (arr[0] == target) return 0;
int i = 1;
while (i < n && arr[i] <= target) i *= 2;
return binarySearch(arr, i / 2, i < n ? i : n – 1, target);
}
int main() {
int arr[] = {10, 20, 30, 40, 50, 60, 70};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 50;
int result = exponentialSearch(arr, n, target);
if (result != -1) {
printf(“Element found at index %d\n”, result);
} else {
printf(“Element not found\n”);
}
return 0;
}
Summary of Searching Methods:
| Search Type | Best Case | Worst Case | Requires Sorted Data | Use Case |
| Linear Search | O(1)O(1)O(1) | O(n)O(n)O(n) | No | Unsorted data, small datasets. |
| Binary Search | O(1)O(1)O(1) | O(logn)O(\log n)O(logn) | Yes | Large sorted arrays. |
| Jump Search | O(1)O(1)O(1) | O(n)O(\sqrt{n})O(n) | Yes | Faster alternative to Linear. |
| Interpolation Search | O(1)O(1)O(1) | O(n)O(n)O(n) | Yes, uniform distribution | Optimized for uniform data. |
| Exponential Search | O(logn)O(\log n)O(logn) | O(logn)O(\log n)O(logn) | Yes | Efficient for sorted data. |
Each method has its strengths and is chosen based on the data type and structure, as well as the specific use case.