🔍 Linear Search vs Binary Search:

Searching algorithms are fundamental to computer science, and among the simplest yet most effective ones are Linear Search and Binary Search. In this blog, we will explore the key differences, implementations in various languages (C, C++, Java, Python, JavaScript), and their time complexities.

What is Linear Search?

Linear Search is the simplest searching algorithm. It traverses the array or list sequentially from the beginning to the end, checking each element until the target value is found or the list ends.

🔹 Time Complexity:

Best Case: O(1) — Target is the first element.
Average Case: O(n) — Target is in the middle.
Worst Case: O(n) — Target is the last element or not present.

🔹 Space Complexity:

O(1) — No extra space is required.

🚀 Implementations of Linear Search:

#include <stdio.h>
 
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target)
            return i; // Target found
    }
    return -1; // Target not found
}
 
int main() {
    int arr[] = {10, 23, 45, 70, 11, 15};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 70;
    int result = linearSearch(arr, n, target);
    printf("Element found at index: %d\n", result);
    return 0;
}

#include <iostream>
using namespace std;
 
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target)
            return i;
    }
    return -1;
}
 
int main() {
    int arr[] = {10, 23, 45, 70, 11, 15};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 70;
    int result = linearSearch(arr, n, target);
    cout << "Element found at index: " << result << endl;
    return 0;
}

public class Main {
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target)
                return i;
        }
        return -1;
    }
 
    public static void main(String[] args) {
        int[] arr = {10, 23, 45, 70, 11, 15};
        int target = 70;
        int result = linearSearch(arr, target);
        System.out.println("Element found at index: " + result);
    }
}

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1
 
arr = [10, 23, 45, 70, 11, 15]
target = 70
result = linear_search(arr, target)
print(f"Element found at index: {result}")

function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i;
        }
    }
    return -1;
}
 
const arr = [10, 23, 45, 70, 11, 15];
const target = 70;
console.log("Element found at index:", linearSearch(arr, target));

🧐 What is Binary Search?

Binary Search is an efficient searching algorithm that works on sorted arrays. It divides the search space into two halves, significantly reducing the search time at each step.

🔹 Time Complexity:

Best Case: O(1) — Target is the middle element.
Average Case: O(log n) — Halves the array every iteration.
Worst Case: O(log n) — Target is not present.

🔹 Space Complexity:

O(1) for iterative.
O(log n) for recursive (due to call stack).

🚀 Implementations of Binary Search:

#include <stdio.h>
 
int binarySearch(int arr[], int low, int high, int target) {
    while (low <= high) {
        int mid = low + (high - low) / 2;
 
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}
 
int main() {
    int arr[] = {10, 23, 45, 70, 100, 150};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 70;
    int result = binarySearch(arr, 0, n - 1, target);
    printf("Element found at index: %d\n", result);
    return 0;
}

#include <iostream>
using namespace std;
 
int binarySearch(int arr[], int low, int high, int target) {
    while (low <= high) {
        int mid = low + (high - low) / 2;
 
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

import java.util.Arrays;
 
public class Main {
    public static int binarySearch(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == target) return mid;
            if (arr[mid] < target) low = mid + 1;
            else high = mid - 1;
        }
        return -1;
    }
}

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

function binarySearch(arr, target) {
    let low = 0, high = arr.length - 1;
    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

📌 Conclusion

Linear Search: Easy to implement, works on unsorted lists, but is slower (O(n)).
Binary Search: Much faster (O(log n)) but requires sorted arrays.

Thanks! For reading

Linear Search vs Binary Search

Linear Search vs Binary Search

Short on Time?? Want to read Offline??

Related Posts