C Program to Implement Binary Search

Introduction

Binary search is an efficient algorithm for finding an item from a sorted list of elements. It works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, the search focuses on the left half, or if the search key is greater, it focuses on the right half. This process continues until the value is found or the interval is empty.

Example:

• Input: Sorted array [1, 3, 5, 7, 9], Search key 5
• Output: Index 2 (since 5 is at index 2)

Problem Statement

Create a C program that:

• Implements binary search on a sorted array.
• Takes an array and a key as input.
• Returns the index of the key if found, or -1 if not found.

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h> for standard input-output functions.
2. Implement the Binary Search Function:

• Perform binary search on the array.
• Return the index of the key if found.

3. Create a Main Function: Allow the user to input the array, sort it, and then perform the binary search.

C Program to Implement Binary Search

#include <stdio.h>

// Function to perform binary search
int binarySearch(int arr[], int low, int high, int key) {
    while (low <= high) {
        int mid = low + (high - low) / 2;  // Calculate mid-point

        // Check if key is present at mid
        if (arr[mid] == key) {
            return mid;
        }

        // If key is greater, ignore the left half
        if (arr[mid] < key) {
            low = mid + 1;
        }
        // If key is smaller, ignore the right half
        else {
            high = mid - 1;
        }
    }

    // Key was not found
    return -1;
}

int main() {
    int n, key;

    // Input the size of the array
    printf("Enter the number of elements in the array: ");
    scanf("%d", &n);

    int arr[n];

    // Input the elements of the array
    printf("Enter %d elements in sorted order:\n", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    // Input the key to be searched
    printf("Enter the key to search: ");
    scanf("%d", &key);

    // Perform binary search
    int result = binarySearch(arr, 0, n - 1, key);

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

    return 0;  // Return 0 to indicate successful execution
}

Explanation

Function to Perform Binary Search

• The binarySearch function takes an array, the lower and upper bounds (low and high), and the key to be searched as inputs.
• The function calculates the mid-point of the array. If the key matches the middle element, its index is returned.
• If the key is greater than the middle element, the search continues in the right half by adjusting low.
• If the key is smaller, the search continues in the left half by adjusting high.
• If the key is not found, the function returns -1.

Main Function

• The main function prompts the user to input the size of the array and the array elements.
• The array elements are assumed to be in sorted order.
• The user then inputs the key they wish to search for.
• The binary search is performed, and the result is displayed, showing either the index of the key or a message indicating that the key was not found.

Output Example

Example Output:

Enter the number of elements in the array: 5
Enter 5 elements in sorted order:
1 3 5 7 9
Enter the key to search: 5
Key 5 found at index 2.

Example Output (Key Not Found):

Enter the number of elements in the array: 5
Enter 5 elements in sorted order:
1 3 5 7 9
Enter the key to search: 4
Key 4 not found in the array.

Conclusion

This C program demonstrates how to implement binary search on a sorted array. Binary search is an efficient algorithm with a time complexity of O(log n), making it ideal for searching in large datasets. This program is a useful example for understanding how to implement and use binary search in C programming.