# 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

**Initialize the search range**: Start with the whole array.**Calculate the middle element**: Find the middle element of the array.**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.

**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

**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.- 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`

.

**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.