# Implementing Binary Search in C: A Step-by-Step Guide

Binary search is a powerful algorithm for efficiently finding a specific value within a sorted array. It is significantly faster than linear search, especially for large datasets.

In this article, we will explore the step-by-step process of implementing binary search in the C programming language.

Binary search works by repeatedly dividing the search space in half. It compares the target value to the middle element of the array and eliminates half of the remaining elements based on the comparison. The process continues until the target is found or the search space is empty.

Here is the general algorithm for binary search:

1. Initialize: Set the lower bound (`low`) to the first index, the upper bound (`high`) to the last index, and the middle index (`mid`) to the middle of the array.
2. Compare: Compare the middle element to the target value.
• If they are equal, the target is found, and its index is returned.
• If the middle element is greater than the target, update the `high` index to `mid - 1` (search the left half).
• If the middle element is less than the target, update the `low` index to `mid + 1` (search the right half).
3. Repeat: Repeat steps 1 and 2 until the target is found or the `low` index is greater than the `high` index.

## Implementation in C

Let's implement binary search in C with a simple example:

``````#include <stdio.h>

int binarySearch(int arr[], int size, int target) {
int low = 0;
int high = size - 1;

while (low <= high) {
int mid = low + (high - low) / 2;

// Check if the target is equal to the middle element
if (arr[mid] == target) {
return mid; // Target found
}

// If the target is greater, ignore the left half
if (arr[mid] < target) {
low = mid + 1;
}

// If the target is smaller, ignore the right half
else {
high = mid - 1;
}
}

}

int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 7;

int result = binarySearch(arr, size, target);

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

return 0;
}
``````

This code defines a function `binarySearch` that takes a sorted array, its size, and a target value as input.

The `main` function demonstrates the usage by searching for a target value in a sorted array.

## Key Points to Note

1. Precondition: Sorted Array

• Binary search assumes that the input array is sorted. If the array is unsorted, the algorithm won't work correctly.
2. Mid Calculation

• The calculation of the middle index (`mid`) is crucial. Using `(low + high) / 2` can lead to integer overflow for large arrays. The expression `(low + (high - low) / 2)` is a safer alternative.
3. Loop Conditions

• The loop condition is `low <= high`. This ensures that the search space is not exhausted, and the algorithm continues until the target is found or the search space is empty.
• The `binarySearch` function returns -1 if the target is not found. This is a common convention in C to indicate that the search was unsuccessful.