Program Overview

The binary search algorithm is an efficient method for finding a target value in a sorted array.
It works by repeatedly dividing the search interval in half.
If the target value is less than the middle element, the search continues in the lower half,
otherwise, it continues in the upper half. This process is repeated until the target value is found
or the interval is empty.

Program Structure

#include 

// Function prototype
int binarySearch(int arr[], int size, int target);

int main() {
    int arr[] = {2, 3, 4, 10, 40}; // Sorted array
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 10; // Element to be searched
    int result = binarySearch(arr, size, target);

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

// Function to perform binary search
int binarySearch(int arr[], int size, int target) {
    int left = 0; 
    int right = size - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2; // Avoids potential overflow

        // Check if the target is present at mid
        if (arr[mid] == target) {
            return mid; // Target found
        }

        // If target is greater, ignore left half
        if (arr[mid] < target) {
            left = mid + 1;
        } 
        // If target is smaller, ignore right half
        else {
            right = mid - 1;
        }
    }
    return -1; // Target not found
}

Code Explanation

• Header Files: The program includes the stdio.h header file for input and output functions.
• Function Prototype: The prototype for the binarySearch function is declared at the top.
• Main Function:
  • An integer array arr is initialized with sorted values.
  • The size of the array is calculated.
  • The target value to be searched is specified.
  • The binarySearch function is called and the result is checked.
• Binary Search Function:
  • The function takes the array, its size, and the target value as arguments.
  • It initializes two pointers, left and right, to track the current search range.
  • A loop runs as long as left is less than or equal to right.
  • The midpoint is calculated, and the target is compared to the middle element.
  • Depending on the comparison, either the left or right half is eliminated from consideration.
  • If the target is found, the index is returned; otherwise, -1 is returned when the target is not found.

Conclusion

The binary search algorithm is a powerful searching technique, especially useful for large datasets.
By reducing the search space in half with each iteration, it provides a significant performance improvement
over linear search methods, particularly when working with sorted data.