Search Algorithms in C: Linear Search and Binary Search

In programming, search algorithms are a crucial part. They are used to find specific elements within a dataset. In C, the two most commonly used search algorithms are linear search and binary search. This article will detail these two algorithms and provide corresponding code examples.

1. Linear Search

1.1 Overview

Linear search is a simple search method that checks each element in an array one by one until the target value is found or the entire array is traversed. This method is suitable for both unordered and ordered datasets, but it is less efficient.

1.2 Algorithm Steps

  1. Start from the first element of the array.
  2. Check if the current element is equal to the target value.
  3. If equal, return the position of that element.
  4. If not equal, continue checking the next element.
  5. Repeat steps 2-4 until the target value is found or the entire array is traversed.

1.3 Time Complexity

  • Worst case: O(n), when the target value is at the last position or does not exist.
  • Average case: O(n).

1.4 Example Code

Below is an example code implementing linear search in C:

#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 found position        }    }    return -1; // Return -1 if not found}
int main() {    int arr[] = {10, 20, 30, 40, 50};    int size = sizeof(arr) / sizeof(arr[0]);    int target = 30;
    int result = linearSearch(arr, size, target);
    if (result != -1) {        printf("Element found at index: %d\n", result);    } else {        printf("Element not found.\n");    }
    return 0;}

2. Binary Search

2.1 Overview

Binary search is an efficient search method that is only applicable to sorted datasets. It reduces the search range by dividing the dataset in half, thereby improving efficiency.

2.2 Algorithm Steps

  1. Determine the middle position of the array (mid).
  2. Compare the value at the middle position with the target value:
  • If equal, return that position.
  • If the target value is less than the value at the middle position, continue searching in the left half.
  • If the target value is greater than the value at the middle position, continue searching in the right half.
  • Repeat steps 1-2 until the target value is found or the range is empty.

    • 2.3 Time Complexity

    • Worst case: O(log n), as the problem size is halved each time.

    2.4 Example Code

    Below is an example code implementing binary search in C:

    #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; // Return the found position        }
        if (arr[mid] < target) {            left = mid + 1; // Continue searching in the right half        } else {            right = mid - 1; // Continue searching in the left half        }    }
    return -1; // Return -1 if not found}
int main() {    int arr[] = {10,20,30,40,50}; // Sorted array    int size = sizeof(arr)/sizeof(arr[0]);
    int target =30;
    int result=binarySearch(arr,size,target);
if(result!=-1){printf("Element found at index: %d\n",result);    }else{printf("Element not found.\n");}
    return 0;}

    Conclusion

    This article introduced two fundamental yet important search algorithms—linear search and binary search. While linear search is simple and easy to understand, it is less efficient; on the other hand, binary search is more efficient but requires the input data to be sorted. In practical applications, it is crucial to choose the appropriate method based on specific needs. I hope this article provides you with a deeper understanding of these two algorithms and that you can apply them in your programming.

    Leave a Comment