Welcome to the world of C Programming! Today, we'll dive into one of the most fundamental and practical topics: C Array Searching. This lesson is tailored for both beginners and intermediates, so let's get started! 📝
<a name="understanding-arrays"></a>
An array is a collection of variables, each identified by an array index. In C, arrays are zero-indexed, meaning the first element's index is 0.
int numbers[5] = {1, 2, 3, 4, 5};In this example, numbers is an array of integers with a maximum size of 5 elements. The array is initialized with the values 1, 2, 3, 4, and 5.
<a name="array-searching-the-basics"></a>
The primary goal of array searching is to find a specific element within an array. We'll focus on two common searching techniques: Linear Search and Binary Search.
Linear Search is a simple and easy-to-understand searching algorithm. It works by iterating through the array from the first element to the last, comparing each element with the target value until a match is found or the end of the array is reached.
#include <stdio.h>
int linearSearch(int arr[], int size, int target) {
for (int i = 0; i < size; i++) {
if (arr[i] == target) {
return i; // return the index if found
}
}
return -1; // return -1 if not found
}In this example, the linearSearch function takes an array, its size, and a target value as arguments. It then iterates through the array using a for loop, comparing each element with the target value. If a match is found, the function returns the index of the matching element. If the end of the array is reached without finding the target value, the function returns -1.
<a name="binary-search"></a>
Binary Search is a more efficient searching algorithm compared to Linear Search. It works by dividing the array into two halves and comparing the target value with the middle element. Depending on the comparison result, the search continues on the appropriate half of the array.
Binary Search can only be applied on sorted arrays, as it assumes that the array is sorted and uses this information to quickly narrow down the search.
#include <stdio.h>
int binarySearch(int arr[], int size, int target, int left, int right) {
if (left > right) {
return -1; // return -1 if not found
}
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid; // return the index if found
}
else if (arr[mid] < target) {
return binarySearch(arr, size, target, mid + 1, right);
}
else {
return binarySearch(arr, size, target, left, mid - 1);
}
}In this example, the binarySearch function takes an array, its size, a target value, and the starting and ending indices as arguments. It first checks if the left index is greater than the right index, indicating that the target value is not found. If the array is not sorted, the function will not work correctly. If the array is sorted, the function recursively divides the array into two halves and compares the target value with the middle element. Depending on the comparison result, the search continues on the appropriate half of the array.
<a name="implementing-linear-search"></a>
Let's implement Linear Search and try it out with an example:
#include <stdio.h>
#define ARRAY_SIZE 10
int main() {
int numbers[ARRAY_SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int target = 7;
int index = linearSearch(numbers, ARRAY_SIZE, target);
if (index != -1) {
printf("Found %d at index %d.\n", target, index);
}
else {
printf("Not found.\n");
}
return 0;
}
int linearSearch(int arr[], int size, int target) {
for (int i = 0; i < size; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}In this example, we have an array of 10 integers, and we're searching for the number 7. When you run this code, it should output: Found 7 at index 5.
<a name="implementing-binary-search"></a>
Now let's implement Binary Search and try it out with an example:
#include <stdio.h>
#define ARRAY_SIZE 10
int main() {
int numbers[ARRAY_SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int target = 7;
int index = binarySearch(numbers, ARRAY_SIZE, target, 0, ARRAY_SIZE - 1);
if (index != -1) {
printf("Found %d at index %d.\n", target, index);
}
else {
printf("Not found.\n");
}
return 0;
}
int binarySearch(int arr[], int size, int target, int left, int right) {
if (left > right) {
return -1;
}
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
}
else if (arr[mid] < target) {
return binarySearch(arr, size, target, mid + 1, right);
}
else {
return binarySearch(arr, size, target, left, mid - 1);
}
}In this example, we have the same array as before, and we're searching for the number 7. When you run this code, it should output: Found 7 at index 5.
<a name="optimizing-search-algorithms"></a>
Binary Search is faster than Linear Search because it narrows down the search space with each comparison. However, it requires a sorted array and performs worse on unsorted arrays. In contrast, Linear Search can be used on unsorted arrays but has a worse time complexity.
When working with large datasets, it's essential to sort the array before searching, as this can significantly improve the performance of your code.
<a name="quiz-time"></a>
Which searching algorithm is faster for sorted arrays?
Which searching algorithm can be used on unsorted arrays?