Searching for an element in an array is a common task in programming. When working with arrays in C, we often need to find if a specific element exists in the array.
In this article, we will discuss how to search for elements in an array in C using two methods – linear search and binary search.
About Searching an Element in an Array
Being able to efficiently search for an element in an array is crucial for many algorithms and programs. For example, suppose we have an array of integers, and we want to check if a certain number is present in the array. Or consider an array of strings where we need to find if a given string exists.
We will explore two techniques to search for elements in an array in C – linear search and binary search. Both have their own advantages and limitations, which we will discuss in detail. Understanding these search methods will allow you to choose the right approach for your program based on the problem at hand.
Prerequisites
To follow along with the C programs for searching arrays in this article, you should have the following:
- Basic knowledge of C programming
- Experience with arrays, loops, and conditional statements in C
- A C compiler installed on your system
- A code editor or IDE for writing and editing C code
With these prerequisites met, you will be able to write, compile, and run the example programs presented.
Logic to Search Element in Array
The general logic for searching an element in an array is:
- Get the target element to search for
- Traverse through the array
- Compare each element of the array with the target element
- Return the index of the matched element if a match is made.
- If no match is found after traversing the complete array, return -1 or print element not found.
The traversal and comparison of array elements form the crux of the search process. The effectiveness of the search depends on how we traverse the array and make comparisons.
Method 1: Linear Search
Concept of Linear Search
In linear search, we sequentially traverse through the array and compare each element with the target element one by one. The array is searched in a linear manner from the start to the end. Linear search checks each element of the array one by one sequentially. It can work on both sorted and unsorted arrays.
Algorithm for Linear Search
The algorithm for linear search is:
1. Set index to 0
2. If index equals array size, element not found, terminate
3. Compare array[index] with target element
4. If a match is found, return the index
5. Increment index by 1
6. Go to step 2
Step-by-Step Explanation
Let’s understand this with an example array {10, 45, 32, 98, 67} and target element 32:
- Start from index 0, compare 10 with 32 (no match)
- Move to index 1, compare 45 with 32 (no match)
- Move to index 2, compare 32 with 32 (match found)
- Return index 2
As we can see, we traverse the array sequentially until a match is found. If no match is found, the algorithm terminates after traversing the complete array.
C Program for Linear Search
Program Explanation:
- The program defines a linearSearch function to search for an element in an integer array sequentially.
- It uses a for loop to iterate through the array elements and checks if the current element matches the target element.
- The main function initializes an array, specifies an element to find, and calls the linearSearch function.
- If the element is found, it prints the index where it’s located; otherwise, it indicates that the element was not found.
- The program returns 0 after completing its task.
Here is a sample C program to implement linear search:
#include <stdio.h>
int linearSearch(int arr[], int size, int element) {
for(int i = 0; i < size; i++) {
if(arr[i] == element) {
return i;
}
}
return -1;
}
int main() {
int arr[] = {10, 45, 32, 98, 67};
int size = sizeof(arr) / sizeof(arr[0]);
int element = 32;
int index = linearSearch(arr, size, element);
if(index != -1) {
printf("Element found at index: %d", index);
} else {
printf("Element not found");
}
return 0;
}
Sample Input-Output
Input: arr[] = {10, 45, 32, 98, 67}, element = 32
Output: Element found at index: 2
Time Complexity
The time complexity of a linear search is O(n) because, in the worst-case scenario, it necessitates scanning the complete array once to locate the desired element.
Types of Linear Search
1) Basic C Program to Find an Element in an Array
This program demonstrates the basic linear search technique to find an element in an array.
In a linear search, each element of the array is examined one by one until either the target element is discovered or all elements have been inspected.
#include <stdio.h>
int main() {
int arr[] = {12, 45, 32, 67, 89};
int n = sizeof(arr)/sizeof(arr[0]);
int searchKey = 32;
for(int i=0; i<n; i++) {
if(arr[i] == searchKey) {
printf("Element found at index %d", i);
return 0;
}
}
printf("Element not found");
return 0;
}
Output:
Element found at index 2
2) C program to search an element in an array using a function
This program shows how to implement linear search using a function.
The search logic is abstracted into a separate function for modularity and reusability.
#include <stdio.h>
int search(int arr[], int n, int key) {
for(int i=0; i<n; i++) {
if(arr[i] == key) {
return i;
}
}
return -1;
}
int main() {
int arr[] = {45, 32, 12, 67, 89};
int n = sizeof(arr)/sizeof(arr[0]);
int searchKey = 12;
int index = search(arr, n, searchKey);
if(index != -1) {
printf("Element found at index %d", index);
}
else {
printf("Element not found");
}
return 0;
}
Output:
Element found at index 2
3) C program to search an element in an array using recursion
This program implements linear search recursively.
Recursion involves a process in which a function repeatedly invokes itself, and this recursive approach can also be applied to implement linear search.
#include <stdio.h>
int search(int arr[], int i, int n, int key) {
if(i >= n) {
return -1;
}
if(arr[i] == key) {
return i;
}
return search(arr, i+1, n, key);
}
int main() {
int arr[] = {45, 32, 12, 67, 89};
int n = sizeof(arr)/sizeof(arr[0]);
int searchKey = 67;
int index = search(arr, 0, n, searchKey);
if(index != -1) {
printf("Element found at index %d", index);
}
else {
printf("Element not found");
}
return 0;
}
Output:
Element found at index 3
Method 2: Binary Search
Concept of Binary Search
In binary search, we leverage the fact that the array is already sorted to optimize the search process. We repeatedly divide the search space (array) in half based on comparisons with middle element. Binary search utilizes the sorted order of elements to quickly narrow down the search space. It only works on sorted arrays.
Algorithm for Binary Search
The algorithm for binary search is:
1. Set lower index to 0, upper index to size of array – 1
2. Find middle index: mid = (lower + upper)/2
3. Compare array[mid] with target element
a) If match, return mid
b) If target < array[mid], set new upper = mid – 1
c) If target > array[mid], set new lower = mid + 1
4. Repeat steps 2 and 3 until match is found or low > high
Step-by-Step Explanation
Let’s take the same example array, which is now sorted {10, 32, 45, 67, 98}. The target element is 32:
1. low = 0, high = 4, mid = (0 + 4) / 2 = 2
2. array[mid] = 45, which is > target (32)
3. So we set new high = mid – 1 = 1
4. low = 0, high = 1, mid = (0 + 1) / 2 = 0
5. array[mid] = 10, which is < target (32)
6. So we set new low = mid + 1 = 1
7. low = 1, high = 1, mid = (1 + 1) / 2 = 1
8. array[mid] matches target element. Return index 1.
As we can observe, binary search narrows down the search space at each iteration using comparisons with middle element.
C Program for Binary Search
Program Explanation:
- The program defines a binarySearch function to search for an element in a sorted integer array.
- It uses a while loop to efficiently narrow down the search range.
- The main function initializes an array, specifies an element to find, and calls the binarySearch function.
- If the element is found, it prints the index where it’s located; otherwise, it indicates that the element was not found.
- The program returns 0 after completing its task.
#include <stdio.h>
int binarySearch(int arr[], int size, int element) {
int low = 0;
int high = size - 1;
while(low <= high) {
int mid = (low + high) / 2;
if(arr[mid] == element) {
return mid;
}
if(arr[mid] < element) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
int main() {
int arr[] = {10, 32, 45, 67, 98};
int size = sizeof(arr) / sizeof(arr[0]);
int element = 32;
int index = binarySearch(arr, size, element);
if(index != -1) {
printf("Element found at index: %d", index);
} else {
printf("Element not found");
}
return 0;
}
Sample Input-Output
Input: arr[] = {10, 32, 45, 67, 98}, element = 32
Output: Element found at index: 1
Time Complexity
Binary search exhibits a time complexity of O(log n) because it consistently divides the search area into two equal parts during each step of the process.
Differences Between Linear and Binary Search
| Linear Search | Binary Search |
| Works on both sorted and unsorted arrays | Requires array to be sorted |
| Traverses array sequentially from start to end | Uses divide and conquer to narrow search |
| Time complexity is O(n) | Time complexity is O(log n) |
| Simple implementation | More complex implementation |
To summarize, linear search is simpler but slower for large arrays. Binary search is faster but requires the array to be sorted.
Conclusion
Searching arrays efficiently is key to many algorithms. This article explored linear and binary search – two fundamental techniques with distinct tradeoffs. Linear search is simple to implement but inefficient for large arrays. Binary search is faster logarithmically but requires a sorted array. Choosing the right search method requires weighing simplicity against performance. With practice, one can adeptly apply these foundational C array search techniques to tackle programming problems.