Search Algorithms in C: Implementation of Linear Search and Binary Search

In computer science, search algorithms are used to find specific data items within data structures. In this article, we will explain two fundamental search algorithms: linear search and binary search. We will provide code examples in C, suitable for beginners to understand.

1. Linear Search

1.1 What is Linear Search?

Linear search is a simple search method. It checks each element in the array one by one and returns the position of the element when the target value is found. If the entire array is traversed without finding the target value, it returns a value indicating that the target was not found, such as -1.

1.2 Time Complexity of Linear Search

In the worst case, all n elements need to be checked, so its time complexity is O(n).

1.3 C Implementation

Here is an example code implementing linear search in C:

#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; // Found the target value, return position        }    }    return -1; // Target value not found}
int main() {    int arr[] = {5, 3, 8, 4, 2};    int size = sizeof(arr) / sizeof(arr[0]);    int target = 4;
    int result = linear_search(arr, size, target);
    if (result != -1) {        printf("Element %d is at position: %d\n", target, result);    } else {        printf("Element %d not found in the array\n", target);    }
    return 0;}

Explanation:

linear_search function takes an integer array, its size, and a target value as parameters.
It uses a for loop to traverse the entire array, returning the current index if the current element equals the target.
If the loop ends without finding the target, it returns -1.

2. Binary Search

2.1 What is Binary Search?

Binary search is an efficient search algorithm, but it requires the input data to be sorted beforehand. It reduces the search range by dividing the query range in half, thus lowering the time complexity.

2.2 Time Complexity of Binary Search

Since each comparison reduces the interval to be processed by half, its time complexity is O(log n).

2.3 C Implementation

Here is an example code implementing binary search in C:

#include <stdio.h>
int binary_search(int arr[], int size, int target) {    int left = 0;    int right = size - 1;
    while (left <= right) {        int mid = left + (right - left) / 2; // Prevent overflow
        if (arr[mid] == target)            return mid; // Found the target value, return position
        if (arr[mid] < target)            left = mid + 1; // Adjust left boundary        else            right = mid - 1; // Adjust right boundary   }
   return -1; // Target value not found }
int main() {    int arr[] = {2,4,5,8,9}; // Note: The array must be sorted    int size = sizeof(arr)/sizeof(arr[0]);    int target=8;
    int result=binary_search(arr,size,target);
    if(result!=-1){        printf("Element %d is at position: %d\n",target,result);   }else{        printf("Element %d not found in the array\n",target);   }
   return 0;}

### Explanation:

binary_search function also takes a sorted integer array, its size, and a target value as parameters.
It defines left and right pointers (left and right), which mark the boundaries of the current search interval. Inside the while loop, it checks the position of mid, and based on the value at mid, it adjusts the left or right pointer direction to cover a smaller area in the next check.

Conclusion

This article introduced two basic and common string search methods—linear search and binary search, and provided related implementation schemes, including the coding process. Readers are encouraged to further explore other advanced topics; otherwise, the above methods should be preferred to address various basic issues. In future studies of advanced programming and optimization, algorithm analysis techniques and details are also very important. We hope this helps you better understand C programming knowledge and solve problems in daily development work.