Binary Search in C

Binary Search in C: Binary search is an efficient algorithm for finding an item from a sorted list of items. 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 continues in the lower half, or if it is greater, it continues in the upper half. This process repeats until the value is found or the interval is empty. Remember if your list of items in not in sorted order, Binary search will not work.

Here’s a step-by-step explanation and an example implementation in C:

How Binary Search in C works

1. Initialize the search range: Start with the whole array.
2. Calculate the middle element: Find the middle element of the array.
3. Compare the middle element with the target value:
   • If the middle element is the target value, the search is complete.
   • If the target value is less than the middle element, narrow the search to the lower half of the array.
   • If the target value is greater than the middle element, narrow the search to the upper half of the array.
4. Repeat: Continue the process with the new search range until the target value is found or the range is empty.

Example of Binary Search in C

Here is a simple C program that demonstrates binary search:

#include <stdio.h>

// 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;

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

        // 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;
        }
    }

    // Target is not present in the array
    return -1;
}

int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 10;
    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;
}

Explanation

1. Initialization: The array arr[] is initialized with sorted values, and size is the number of elements in the array. target is the value we want to search for.
2. Binary Search Function
   • left and right variables represent the current search range.
   • The while loop continues as long as left is less than or equal to right.
   • mid is calculated to be the middle index of the current range.
   • If the middle element is the target, return the index mid.
   • If the target is greater than the middle element, narrow the search to the upper half by setting left = mid + 1.
   • If the target is smaller, narrow the search to the lower half by setting right = mid - 1.
3. Main Function: Calls the binarySearch function and checks the result. If the result is not -1, it means the element is found, otherwise, it is not present in the array.

This program demonstrates the basic concept of binary search and how it can be implemented in C.

Each step of the algorithm divides the block of items being searched in half. We can divide a set of n items half at most log n times. Thus the running time of a binary search is proportional to log n and we say this is a O(log n) algorithm.