In this article, we will discuss the C program to search for an element in an Array. But before discussing the program, we must know about searching an array with their methods and examples.

What is searching in an array?

Searching in an array is finding a particular element inside the elements of an array. Its main objective is to locate the element's position or index in the array and to ascertain whether the element is present in the array. In computer science, searching is a fundamental process utilized in various algorithms and applications.

You are simply attempting to determine whether element "X" is present in the array when you search in an array. If the element is there, you might also be interested in knowing precisely where it is in the array. There are various array searching techniques, and the algorithm to choose relies on the size of the array, whether it is sorted, and the performance needs of the particular application.

Types of Array Searching

Binary search and linear search are the two most popular array search techniques.

Linear Search:

Sequential Search algorithm is another name for linear search.
It is the most straightforward search algorithm.
In a linear search, we merely go through the list in its whole and match each element with the object whose location needs to be determined.
The algorithm returns the item's location if a match is made; otherwise, it returns NULL.

Binary Search:

The search method that performs well on sorted lists is a binary search.
Therefore, we must ensure the list is sorted before utilizing the binary search strategy to find an element.
The divide and conquer strategy is used in binary search, where the item is compared to the middle element of the list after the list is divided into two halves.
The location of the middle element is returned if a match is discovered.
Otherwise, we search into either of the halves depending on the match's outcome.

Working of Linear Search:

Let's consider an array [12, 45, 7, 23, 56, 89, 34, 18].
Suppose we wish to use the linear search technique to look for element 56 in this array.
Comparing the array's initial member, 12, with the target element, 56, begins at the array's beginning (index 0).
Move on to the element at index 1 and compare 45 with 56 since 12 is not equal to 56.
Once you've found a match or reached the end of the array, carry on in this manner, going through the array one element at a time.
You will ultimately reach element 56 at index 4 after comparing all the elements. The linear search is successful since the target element matches the value at this index.

The breakdown is as follows, step by step:

12 and 56 are comparable. Not the same.
Compare 56 to 45. Not the same.
7 is comparable to 56. Not the same.
23 and 56 is comparable. Not the same.
56 is comparable to 56.
At index 4, the target element 56 can be found.
Until the target element is located or the array's end is reached, the linear search algorithm sequentially scans through each Element. In this instance, it took four comparisons to locate the desired element 56 at index 4.

C Program to implement Linear Search in an Array:

#include <stdio.h>

int linear search(int arr[], int size, int target) {

 for (int i = 0; i < size; ++i) {

 if (arr[i] == target) {

 return i; //Element found, return its index

 }

 }

 return -1; // Element not found

}

int main() {

 int size;

printf("Enter the size of the array: ");

scanf("%d", &size);

 int arr[size];

printf("Enter %d elements:\n", size);

 for (int i = 0; i < size; ++i) {

scanf("%d", &arr[i]);

 }

 int target;

printf("Enter the target element: ");

scanf("%d", &target);

 int index = linearSearch(arr, size, target);

 if (index != -1) {

printf("Element found at index: %d\n", index);

 } else {

printf("Element not found\n");

 }

 return 0;

}

Output:

C Program to Search an Element in an Array

Linear Search is effective in the following cases:

Small Arrays:

When working with small arrays, it may not be necessary to construct more complicated search methods. Because of its simplicity and practicality, linear search is a viable option in certain circumstances.

Unsorted Arrays:

Unsorted arrays can benefit from the usage of linear search. Linear search is a good choice if the array is not sorted and you don't want to take the extra sorting step.

Simplicity:

It's important to keep things simple because linear search is an easy method to use and comprehend. Linear search can be a viable option if maintaining code simplicity is a top goal and the size of the data set is not too enormous.

Multiple Occurrence Search:

Linear search can be readily modified to locate every instance of a target element. It might keep searching the entire array to find all matching elements.

When Time Complexity Is Not Critical:

The higher time complexity of linear search (O(n)) may not have a major effect on overall performance when the array size is modest, or the number of search operations is constrained.

When the Array is constantly changing:

The simplicity and versatility of linear search might be useful when searching an array that is often updated or modified.

Time complexity:

Best-case Time Complexity (Element Found at the Beginning):

The procedure would only need one comparison if the target element were located at the very beginning of the array.
In this situation, the best-case time complexity is O(1), which denotes continuous time.

Worst-case Time Complexity (Element Not Found or Found at the End):

In the worst situation, the linear search method could need to compare the target element with each element in the array before concluding that the element is absent.
It necessitates "n" comparisons, where "n" is the array's element count. The worst-case time complexity, which denotes linear time, is O(n).

Average-case Time Complexity:

A linear search would typically need to look at about half of the elements in an array when considering all scenarios (including successful and unsuccessful searches) and assuming an equitable distribution of targets in the array.
It leads to an average-case time complexity of O(n/20), which reduces to O(n) due to how big-O notation treats constants.

Working of Binary Search:

Binary search is particularly efficient for sorted arrays. Consider the following sorted array:

[3, 8, 15, 25, 33, 47, 56, 68, 72, 89]

Let's say we want to search for element 47 in this array using the binary search algorithm.

Initial step:

Calculate the index in the middle of the array. For this example, (0 + 9)/2 = 4, so the middle index is 4.
Compare the middle element 33 with the target element 47.

Compare:

Since 33 is less than 47, we know that the target element, if any, must be in the right half of the array.

Update search scope:

Remove the left half of the array (elements [3, 8, 15, 25]) because they are smaller than the target, and the new search range becomes [47, 56, 68, 72, 89].
Calculate a new median for the reduced search coverage. (4 + 9)/2 = 6, so the new median index is 6.
Compare median element 56 with target element 47.

Compare:

Since 56 is greater than 47, we know that the target element, if any, must be in the left half of the other array.

Update search scope:

Remove the right half of the array (items [68, 72, 89]) because they are larger than the target, and the new search range becomes [47].
Calculate a new average for the remaining one-item search range. (4 + 5)/2 = 4, so the new median index is 4. Compare median element 47 with target element 47.

Compare:

Center element 47 corresponds to target element 47. We have found the element we are looking for. The binary search algorithm successfully located target 47 in only three iterations. Here is a summary of the steps:
The middle element is 33 (less than 47) -> Find the right half.
The middle element is 56 (greater than 47) -> Find the left half.
The middle element is 47 (match) -> Item found.

Binary search has a time complexity of O(log n), where n is the number of elements in the array. It makes it significantly more efficient than linear search, especially for large arrays.

Example: C Program to implement Binary Search in an Array:

#include <stdio.h>

int binarySearch(int arr[], int size, int target) {

 int left = 0;

 int right = size - 1;

 while (left <= right) {

 int mid = left + (right-left) / 2;

 if (arr[mid] == target) {

 return mid; //Element found, return its index

 }

 if (arr[mid] < target) {

 left = mid + 1; // Search in the right half

 } else {

 right = mid - 1; // Search in the left half

 }

 }

 return -1; // Element not found

}

int main() {

 int size;

printf("Enter the size of the sorted array: ");

scanf("%d", &size);

 int arr[size];

printf("Enter %d sorted elements:\n", size);

 for (int i = 0; i< size; ++i) {

scanf("%d", &arr[i]);

 }

 int target;

printf("Enter the target element: ");

scanf("%d", &target);

 int index = binarySearch(arr, size, target);

 if (index != -1) {

printf("Element found at index: %d\n", index);

 } else {

printf("Element not found\n");

 }

 return 0;

}

Output:

Binary Search is Effective in the following cases:

Sorted Tables:

Binary search is most efficient when applied to sorted arrays. It takes advantage of sorted order to remove half of the remaining elements at each step, which makes it significantly faster than linear search.

Big data sets:

Binary search shines in large data sets as shrinking the search space at each step quickly narrows the possibilities. Its logarithmic time complexity (O(log n)) ensures that even with large inputs, the number of comparisons is still manageable.

Frequent search operations:

If you need to perform multiple searches on the same sorted data set, the binary search can provide significant time savings compared to linear search.

Memory usage:

Binary search does not require additional data structures such as hash tables, which makes it memory efficient. It operates directly on arrays, which is especially useful in memory-constrained environments.

Ordered data:

When dealing with data that can be naturally ordered, such as numeric or alphabetic data, binary search provides an efficient and systematic way to locate specific items.

Time complexity:

Best case time complexity (Element found in the middle):

In the best case, the target element is exactly in the middle of the array.
It results in a single comparison.
In the best case, the binary search time complexity is O(1), representing constant time.

Worst case time complexity (Element not found or not found at endpoints):

In the worst case, the target element is not in the array or is at one of the ends of the array.
In this case, the binary search will keep dividing the array until the search space is reduced to one element.
The worst-case binary search time complexity is O(log n), where "n" is the number of elements in the array.

Average time complexity:

On average, binary search halves the search space with each comparison.
It leads to the logarithmic behavior of the algorithm. The average time complexity of a binary search is also O(log n).

The time complexity of O(log n) binary search makes it significantly more efficient than linear search, especially for large data sets. The logarithmic behavior ensures that the number of comparisons remains relatively low even as the size of the array increases. It's important to note that binary search requires the array to be sorted. If the array is unsorted, a pre-sorting step must be performed, which adds to the O(n log n) time complexity to sort. However, after sorting, the effect of binary search becomes apparent during the search.

← Prev Next →

C Tutorial

C Tutorial

C Program to Search an Element in an Array

What is searching in an array?

Types of Array Searching

Linear Search:

Binary Search:

Working of Linear Search:

C Program to implement Linear Search in an Array:

Linear Search is effective in the following cases:

Time complexity:

Working of Binary Search:

Binary Search is Effective in the following cases:

Time complexity: