DSA Tutorial

Types of Searching

• Linear Search: Traverse through each element in an unsorted list until the element is found.
• Binary Search: Efficiently search a sorted list by repeatedly dividing the search interval in half.

📘 Linear Search

Linear Search is a simple method to find an element in an unsorted array by checking each element sequentially.

1. Start from the first element of the array.
2. Compare the current element with the target element.
3. If found, return the index of the element.
4. If not found, move to the next element and repeat until the target is found or the end is reached.
    

#include <stdio.h>

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;  // Element found, return index
        }
    }
    return -1;  // Element not found
}

int main() {
    int arr[] = {3, 5, 7, 9, 11, 13};
    int n = 6;
    int target = 9;
    int result = linearSearch(arr, n, target);

    if (result != -1)
        printf("Element found at index %d\n", result);
    else
        printf("Element not found\n");

    return 0;
}
      

📘 Binary Search

Binary Search is a much faster method for finding an element in a sorted array. It works by dividing the array into two halves and recursively searching the relevant half.

1. Start with the middle element of the array.
2. If the target is equal to the middle element, return the index.
3. If the target is smaller than the middle element, search the left half.
4. If the target is greater, search the right half.
5. Repeat until the element is found or the array is empty.
    

#include <stdio.h>

int binarySearch(int arr[], int low, int high, int target) {
    if (low >= high)
        return -1;

    int mid = low + (high - low) / 2;
    if (arr[mid] == target)
        return mid;  // Element found

    if (arr[mid] > target)
        return binarySearch(arr, low, mid - 1, target);
    else
        return binarySearch(arr, mid + 1, high, target);
}

int main() {
    int arr[] = {2, 5, 9, 14, 23, 34};
    int n = 6;
    int target = 14;
    int result = binarySearch(arr, 0, n - 1, target);

    if (result != -1)
        printf("Element found at index %d\n", result);
    else
        printf("Element not found\n");

    return 0;
}
      

📊 Linear Search vs Binary Search

• Linear Search: Best for unsorted arrays. Time Complexity: O(n)
• Binary Search: Best for sorted arrays. Time Complexity: O(log n)