Searching Algorithms

Searching algorithms are methods for finding specific data within a data structure. They play a crucial role in various applications, such as databases, search engines, and more.

Types of Searching Algorithms

• Linear Search: This algorithm sequentially checks each element of the list until a match is found or the list ends.
• Binary Search: This algorithm divides the list into halves to find the target value quickly. It requires the list to be sorted.

Linear Search

The linear search algorithm is simple and straightforward. It checks each element in the array until it finds the target or reaches the end.

Algorithm Steps

1. Start from the first element.
2. Compare the current element with the target value.
3. If a match is found, return the index of the element.
4. If no match is found, move to the next element and repeat.
5. Continue until the target is found or all elements are checked.

#include <stdio.h>

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

int main() {
    int arr[] = {5, 3, 8, 4, 2};
    int target = 4;
    int size = sizeof(arr) / sizeof(arr[0]);
    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;
}
                    

Binary Search

Binary search is more efficient than linear search, but it requires the array to be sorted. It repeatedly divides the search interval in half.

Algorithm Steps

1. Start with the entire array.
2. Find the middle element of the array.
3. If the middle element equals the target, return its index.
4. If the target is less than the middle element, narrow the interval to the lower half.
5. If the target is greater than the middle element, narrow the interval to the upper half.
6. Repeat until the target is found or the interval is empty.

#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; // Target found
        }
        if(arr[mid] < target) {
            left = mid + 1; // Search in the right half
        } else {
            right = mid - 1; // Search in the left half
        }
    }
    return -1; // Target not found
}
int main() {
    int arr[] = {2, 3, 4, 5, 8}; // Sorted array
    int target = 5;
    int size = sizeof(arr) / sizeof(arr[0]);
    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;
}

Searching algorithms are fundamental in programming. Understanding their mechanisms and efficiencies is key to solving problems effectively. Practice implementing these algorithms and consider their application in different scenarios to deepen your understanding.