Linear Vs Binary

Linear Vs Binary Search + Code in C Language

We have already covered the first three operators in an array, namely traversal, insertion, and deletion. Today, we will learn about the search operations in an array.

You must already be familiar with these two methods we have for searching in an array: linear and binary search. We analyzed them and concluded that for a sorted array, the fastest method to search is the binary one. Today, we’ll learn how to code them and practically use them to search.

Linear Search:

This search method searches for an element by visiting all the elements sequentially until the element is found or the array finishes. It follows the array traversal method.

Binary Search

Binary search efficiently locates an element by repeatedly dividing the search space in half. This method only works on sorted arrays, directing the search left or right based on whether the target element is less than or greater than the midpoint of the current range.

From the above illustrations, we can draw a comparison between both the search methods based on their choice of arrays, operations, and worst-case complexities.

Table 1: Linear Search VS Binary Search

Let us now move on to the coding part of these methods. I have attached the snippet below. Refer to it while understanding. Understanding the code snippet 1:

Linear Search

1. To begin, create an integer function called linearSearch that takes the array, its size, and the target element as parameters.
2. Use a for loop to iterate from the start to the end of the array, checking if the element at the current index matches the target. If a match is found, return the index; otherwise, continue searching.
3. If the loop completes without finding the element, return -1 to indicate that the element is not in the array.

Binary Search

1. Define a function named binarySearch with the same three parameters as the linear search. Initialize three integers: low (the start of the search space), high (the end of the search space), and mid (the middle index calculated as mid = (low + high) / 2).
2. Check if the mid element equals the target. If it does, return the mid index. If the mid element is greater than the target, adjust high to mid - 1 to search the left side. If the mid element is less, adjust low to mid + 1 to search the right side.
3. Repeat this process until the element is found or until low exceeds high, indicating the element is not present in the array.

#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 binarySearch(int arr[], int size, int element){
    int low, mid, high;
    low = 0;
    high = size-1;
    // Keep searching until low <= high
    while(low<=high){
        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(){
    // Unsorted array for linear search
    // int arr[] = {1,3,5,56,4,3,23,5,4,54634,56,34};
    // int size = sizeof(arr)/sizeof(int);
 
    // Sorted array for binary search
    int arr[] = {1,3,5,56,64,73,123,225,444};
    int size = sizeof(arr)/sizeof(int);
    int element = 444;
    int searchIndex = binarySearch(arr, size, element);
    printf("The element %d was found at index %d \n", element, searchIndex);
    return 0;
}

Code Snippet 1: Linear search and Binary search codes. Let’s check if it works. Refer to the output below:

The element 444 was found at index 8 
PS D:\MyData>

So from the above output, you can conclude that our code works all fine. So, implementing both these search methods. Binary Search holds great importance in the world of programming. We’ll come across several algorithms following binary search.