C Program to Implement Binary Search

1. Introduction

Binary Search is an efficient algorithm for finding an item from a sorted list of items. Instead of searching the list in a linear fashion, the algorithm divides the input list in half repetitively until the desired value is found or the entirety of the list has been searched.

2. Program Overview

In this program, we will:

1. Implement the binarySearch function to search for an element in a sorted array.

2. Search for a specified element in the sorted array.

3. Display whether the element is found and its position if it exists.

3. Code Program

#include <stdio.h>

// Function for binary search
int binarySearch(int arr[], int left, int right, int x) {
    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == x) {  // Element found, return index
            return mid;
        }

        if (arr[mid] < x) {
            left = mid + 1;  // Search the right half
        } else {
            right = mid - 1;  // Search the left half
        }
    }

    return -1;  // Element not found, return -1
}

// Driver code
int main() {
    int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 5;  // Element to be searched

    printf("Array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

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

    return 0;
}

Output:

Array: 0 1 2 3 4 5 6 7 8 9
Element 5 is present at index 5.

4. Step By Step Explanation

1. The binarySearch function accepts a sorted array, the left and right boundaries of the current search interval, and the element to be searched for. It then iterates while adjusting the boundaries based on the mid-point comparison.

2. In the main function, we initialize a sorted array and the element we want to search for.

3. We then call the binarySearch function and store the result in the result variable.

4. Based on the result, we print whether the element was found and its position or specify that the element is not present in the array.

Binary Search has a time complexity of O(log n) in the worst case, making it far more efficient than linear search for larger datasets. However, it requires the input array to be sorted.