Binary search is an efficient algorithm used to find a specific element in a sorted array or list. Unlike linear search, which checks each element sequentially, binary search divides the search interval in half, which significantly reduces the number of comparisons needed to find the target value.

Key Characteristics of Binary Search

1. Time Complexity:

   • The time complexity of binary search is $O(\log n)$, where $n$ is the number of elements in the array. This logarithmic performance is what makes binary search much faster than linear search, especially for large datasets.

2. Space Complexity:

   • The space complexity is $O(1)$ for the iterative version, as it only uses a constant amount of additional space. However, the recursive version has a space complexity of $O(\log n)$ due to the call stack.

3. Requirements:

   • The array or list must be sorted before performing a binary search. If the data is not sorted, the results will be incorrect.

Implementation of Binary Search in C

Below is a simple implementation of the binary search algorithm in C, demonstrating both iterative and recursive approaches.

Iterative Binary Search Implementation

#include <stdio.h>

// Function for iterative binary search
int binarySearchIterative(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2; // Calculate the mid index

        // Check if the target is present at mid
        if (arr[mid] == target) {
            return mid; // Return the index of the target if found
        }
        // If target is greater, ignore the left half
        else if (arr[mid] < target) {
            left = mid + 1;
        }
        // If target is smaller, ignore the right half
        else {
            right = mid - 1;
        }
    }
    return -1; // Return -1 if the target is not found
}

int main() {
    int arr[] = {2, 4, 5, 8, 10, 14, 16}; // Sorted example array
    int size = sizeof(arr) / sizeof(arr[0]);
    int target;

    // Ask user for the target value to search
    printf("Enter the number to search: ");
    scanf("%d", &target);

    // Perform binary search
    int result = binarySearchIterative(arr, size, target);

    // Display the result
    if (result != -1) {
        printf("Element found at index: %d\n", result);
    } else {
        printf("Element not found in the array.\n");
    }

    return 0;
}

Recursive Binary Search Implementation

#include <stdio.h>

// Function for recursive binary search
int binarySearchRecursive(int arr[], int left, int right, int target) {
    if (left <= right) {
        int mid = left + (right - left) / 2; // Calculate the mid index

        // Check if the target is present at mid
        if (arr[mid] == target) {
            return mid; // Return the index of the target if found
        }
        // If target is greater, search in the right half
        else if (arr[mid] < target) {
            return binarySearchRecursive(arr, mid + 1, right, target);
        }
        // If target is smaller, search in the left half
        else {
            return binarySearchRecursive(arr, left, mid - 1, target);
        }
    }
    return -1; // Return -1 if the target is not found
}

int main() {
    int arr[] = {2, 4, 5, 8, 10, 14, 16}; // Sorted example array
    int size = sizeof(arr) / sizeof(arr[0]);
    int target;

    // Ask user for the target value to search
    printf("Enter the number to search: ");
    scanf("%d", &target);

    // Perform binary search
    int result = binarySearchRecursive(arr, 0, size - 1, target);

    // Display the result
    if (result != -1) {
        printf("Element found at index: %d\n", result);
    } else {
        printf("Element not found in the array.\n");
    }

    return 0;
}

Explanation of the Code

1. Header Files:

   • #include <stdio.h>: Includes the standard input-output library for functions like printf and scanf.

2. Iterative Binary Search Function:

   • binarySearchIterative: This function performs a binary search iteratively. It takes three parameters:
     • An integer array arr[],
     • An integer size representing the number of elements in the array,
     • An integer target which is the value to search for.
   • The function initializes two pointers, left and right, which represent the current search range.
   • It enters a while loop that continues until the left pointer exceeds the right pointer:
     • It calculates the middle index mid.
     • If the middle element equals the target, it returns the index.
     • If the middle element is less than the target, it narrows the search to the right half.
     • If the middle element is greater, it narrows the search to the left half.
   • If the target is not found, it returns -1.

3. Recursive Binary Search Function:

   • binarySearchRecursive: This function performs binary search recursively. It takes four parameters:
     • An integer array arr[],
     • Two integers left and right representing the current search range,
     • An integer target.
   • It checks if the search range is valid (left ≤ right):
     • Similar to the iterative version, it calculates mid and checks if the middle element equals the target.
     • Depending on the comparison, it recursively searches either the left or right half.
   • If the target is not found, it returns -1.

4. Main Function:

   • Initializes a sorted example array arr with some integers.
   • Calculates the size of the array using sizeof(arr) / sizeof(arr[0]).
   • Prompts the user to enter a number to search for.
   • Calls either the iterative or recursive binary search function and stores the result.
   • Displays the index of the found element or a message indicating that the element is not found.

How to Run the Program

1. Compile the Code: Use a C compiler like gcc to compile the code.

   gcc binary_search.c -o binary_search
   

2. Execute the Program:

   ./binary_search
   

3. Input Data: Enter a number when prompted to see if it exists in the array.

Example Input/Output

Input:

Enter the number to search: 10

Output:

Element found at index: 4

Input:

Enter the number to search: 7

Output:

Element not found in the array.

Conclusion

Binary search is a highly efficient algorithm for searching in sorted datasets, reducing the number of comparisons required to find a target value. Its logarithmic time complexity makes it suitable for large arrays, and understanding its implementation is crucial for any programmer dealing with search algorithms.