Implement linear search on an unsorted array using C programming language.

Implement linear search on an unsorted array using C programming language.

Code:

#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 where the target was found
}
}
return -1; // Return -1 if target was not found in the array
}

int main() {
int array[] = {34, 12, 45, 67, 23, 9, 56, 78, 91};
int size = sizeof(array) / sizeof(array[0]);
int target = 23;

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

if (index != -1) {
printf("Target %d found at index %d\n", target, index);
} else {
printf("Target %d not found in the array\n", target);
}

return 0;
}

In this example, the linearSearch function takes an array, its size, and the target value to search for. It iterates through the array, comparing each element with the target value. If the target value is found, it returns the index of that element. If the target value is not found, it returns -1.

In the main function, an array is defined, and the linearSearch function is called to search for a specific target value. The index where the target value is found (or -1 if not found) is then printed to the console.

Remember that linear search is a simple but not very efficient search algorithm, especially for larger arrays. It has a time complexity of O(n), where n is the number of elements in the array. For larger datasets, more efficient search algorithms like binary search or hash tables might be preferred.

Explanation:

#include <stdio.h>

This line includes the standard input/output library, which is necessary for using functions like printf for printing to the console.

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

This line defines the function linearSearch. It takes three arguments: an array arr to search through, an integer size representing the size of the array, and an integer target which is the value we are searching for. The function returns an integer value, which is the index where the target value is found in the array, or -1 if the target value is not found.

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

This line starts a loop that iterates through each index of the array, from 0 to size - 1.

if (arr[i] == target) {

Within the loop, this line checks if the element at the current index (arr[i]) is equal to the target value (target).

return i; // Return the index where the target was found
}

If the current element matches the target value, this line returns the current index i, indicating that the target value was found at that index.

}

The closing brace of the loop indicates the end of the loop. If the loop completes without finding the target value, the function will continue to the next line.

return -1; // Return -1 if target was not found in the array
}

If the loop completes without finding the target value, this line is executed, indicating that the target value was not found in the array. The function returns -1 to signify this.

int main() {

This line starts the main function, which is the entry point of the program. It returns an integer value, which indicates the exit status of the program (usually 0 for successful execution).

int array[] = {34, 12, 45, 67, 23, 9, 56, 78, 91};

Here, an integer array named array is defined and initialized with some values.

int size = sizeof(array) / sizeof(array[0]);

This line calculates the size of the array by dividing the total size of the array by the size of a single element in the array (array[0]). This technique ensures that the program works even if the array size changes.

int target = 23;

The target variable is initialized with the value we want to search for in the array.

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

The linearSearch function is called with the array, size, and target arguments. The returned index (or -1 if not found) is stored in the index variable.

if (index != -1) {
printf("Target %d found at index %d\n", target, index);
} else {
printf("Target %d not found in the array\n", target);
}

Here, an if statement checks whether the index returned by the linearSearch function is not equal to -1. If it's not -1, it means the target was found, and a message is printed indicating the target value and its index. If the index is -1, a message is printed indicating that the target value was not found.

return 0;
}

The main function ends with this line, returning 0 to indicate successful program execution to the operating system.

 

Algorithm:

Algorithm: Linear Search

1. Start

2. Include the necessary header file: #include <stdio.h>

3. Define the function int linearSearch(int arr[], int size, int target)

   1. Initialize a loop variable i from 0 to size - 1

      1. If arr[i] is equal to target

         1. Return the value of i

   2. End loop

   3. Return -1 (target not found)

4. End of linearSearch function

5. Define the main function: int main()

   1. Define an integer array array and initialize it with values

   2. Calculate the size of the array: int size = sizeof(array) / sizeof(array[0])

   3. Define the target value to search for: int target = 23

   4. Call the linearSearch function and store the result in index: int index = linearSearch(array, size, target)

   5. If index is not -1

      1. Print a message indicating the target value and its index

   6. Else

      1. Print a message indicating that the target value was not found

   7. Return 0

6. End of main function

7. End

This algorithm outlines the steps performed in the C program for linear search. It describes how the function linearSearch iterates through the array and compares each element with the target value. If a match is found, it returns the index; otherwise, it returns -1. In the main function, the array is initialized, and the linearSearch function is called to search for the target value. The program then prints the appropriate message based on whether the target value was found or not.

Time Complexity:

The time complexity of the linear search algorithm, as implemented in the above C program, is O(n), where "n" is the number of elements in the array.

Here's why:

In the linear search algorithm, each element of the array is compared with the target value sequentially until a match is found or the end of the array is reached. In the worst case, the algorithm needs to go through all "n" elements of the array to determine that the target value is not present. Therefore, the number of comparisons is directly proportional to the number of elements in the array.

As a result, the time complexity of the linear search algorithm is linear, or O(n), indicating that the number of operations grows linearly with the size of the input data. This makes linear search less efficient for larger datasets compared to algorithms with better time complexities, such as binary search (O(log n)) or hash-based search (O(1) on average with good hash functions).

 

Space Complexity:

The space complexity of the above linear search program is O(1), which means it requires a constant amount of additional space regardless of the size of the input array.

Here's why:

1. Input Data: The array and its size are provided as input to the program. These are not considered part of the space complexity, as they are necessary for the program's operation and do not increase with the size of the input array.

2. Local Variables: Within the linearSearch function, only a few integer variables (i, arr, size, target) are used. These variables occupy a constant amount of space, regardless of the size of the input array.

3. Function Call Stack: The program uses a minimal amount of space on the call stack to manage the function calls and their local variables. Since there is only one recursive function call (main calls linearSearch), and there's no deep nesting of function calls, the space used on the stack remains constant.

In summary, the program doesn't create any dynamically allocated memory, data structures, or arrays that grow with the input size. It only uses a small number of local variables, and the space required for function calls remains constant. Therefore, the space complexity of the program is O(1), indicating a constant amount of space usage regardless of the input size.

 

Thank You