Binary Search in C

Binary search is a search algorithm that excels at finding the position of a specific value (target) within a sorted array.
It works by repeatedly dividing the search interval in half and eliminating the half where the target cannot be by dividing the array into half.
It works only on sorted array.

ARRAY

Collection of elements: Arrays store a fixed-size collection of elements of the same data type under a single variable name.

data_type array_name[size]; 
// Example: int numbers[10];

• Initialization:
  During declaration (optional): int months[12] = {1, 2, 3, ...};
After declaration: months[0] = 1;
• Accessing elements:
  Zero-based indexing: numbers[3] accesses the fourth element.
  Out-of-bounds access leads to undefined behavior.

SEARCH

Linear search: A basic search algorithm that iterates through each element of an array sequentially until the target element is found or the end is reached.

• Time complexity: O(n) in the worst case (target element not present or at the end).
• Not efficient for large arrays.

BINARY SEARCH

• Efficient search for sorted arrays: Only applicable to arrays that are sorted in ascending or descending order.
• Divide-and-conquer approach:

Binary search pseudo code

• Time complexity: O(log n) in the worst and average cases, significantly faster than linear search for large sorted arrays.

#include <stdio.h>

// Function to perform binary search on a sorted array
// Parameters:
// - arr[]: The sorted array to be searched
// - length: Number of elements in the array
// - target: Element to be searched for
// - left: Starting index of the search range
// - right: Ending index of the search range
// Returns the index of the target element if found, otherwise returns -1

int binarySearch(int arr[], int length, int target, int left, int right) {
    while (left <= right) {
        int mid = left + (right - left) / 2; // Calculate the middle index

        if (arr[mid] == target)
            return mid; // Return index of target element if found

        if (arr[mid] < target)
            left = mid + 1; // Adjust left boundary if target is in the right half
        else
            right = mid - 1; // Adjust right boundary if target is in the left half
    }

    return -1; // Return -1 if target element is not found
}

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}; // Sorted array
    int length = sizeof(arr) / sizeof(arr[0]); // Calculate number of elements in arr
    int target = 23; // Element to search for
    int result = binarySearch(arr, length, target, 0, length - 1); // Perform binary search

    if (result == -1)
        printf("Element %d is not present in the array\n", target);
    else
        printf("Element %d is present at index %d\n", target, result);

    return 0;
}

Hereint length = sizeof(arr) / sizeof(arr[0]); calculates the number of elements in the array.

• sizeof(arr): This operator returns the total number of bytes occupied by the array arr in memory. This size includes all elements of the array multiplied by the size of each element.
• sizeof(arr[0]): This operator returns the size of the first element of the array arr. Since arrays in C are contiguous blocks of memory, the size of one element (arr[0]) is the same as the size of all other elements in the array.
• Division: By dividing sizeof(arr) by sizeof(arr[0]), we get the number of elements in the array arr. This calculation works because sizeof(arr) gives us the total size of the array in bytes, and sizeof(arr[0]) gives us the size of one element. Therefore, the division gives us the number of elements (n) in the array arr.
• Example:

int arr[] = {1, 3, 5, 7, 9};

• sizeof(arr) would typically be 5 * sizeof(int) if int occupies 4 bytes in memory (assuming a typical system).
• sizeof(arr[0]) would be sizeof(int).

Therefore, sizeof(arr) / sizeof(arr[0]) would be 5, which is the number of elements in the array arr.

Advantages of sizeof(arr) / sizeof(arr[0]):

1. Compile-Time Computation: This method computes the array size at compile-time, which is efficient and does not require additional runtime calculations.
2. Works with Statically Allocated Arrays: It is well-suited for arrays defined statically within the same scope where their size needs to be determined.
3. Independent of Data Type: It calculates the number of elements regardless of the data type (int, char, etc.) of the array elements.