# Binary Search in C

Binary search is a search algorithm that excels at finding the position of a specific value (target) within a **sorted array**.

It works by repeatedly dividing the search interval in half and eliminating the half where the target cannot be by dividing the array into half.

It works only on sorted array.

## ARRAY

**Collection of elements:** Arrays store a fixed-size collection of elements of the same data type under a single variable name.

`data_type array_name[size]; `

// Example: int numbers[10];

**Initialization:**During declaration (optional):`int months[12] = {1, 2, 3, ...};`

After declaration:`months[0] = 1;`

**Accessing elements:**Zero-based indexing:`numbers[3]`

accesses the fourth element.

Out-of-bounds access leads to undefined behavior.

## SEARCH

**Linear search:** A basic search algorithm that iterates through each element of an array sequentially until the target element is found or the end is reached.

- Time complexity: O(n) in the worst case (target element not present or at the end).
- Not efficient for large arrays.

**BINARY SEARCH**

**Efficient search for sorted arrays:**Only applicable to arrays that are sorted in ascending or descending order.**Divide-and-conquer approach:**

**Time complexity:**O(log n) in the worst and average cases, significantly faster than linear search for large sorted arrays.

`#include <stdio.h>`

// Function to perform binary search on a sorted array

// Parameters:

// - arr[]: The sorted array to be searched

// - length: Number of elements in the array

// - target: Element to be searched for

// - left: Starting index of the search range

// - right: Ending index of the search range

// Returns the index of the target element if found, otherwise returns -1

int binarySearch(int arr[], int length, int target, int left, int right) {

while (left <= right) {

int mid = left + (right - left) / 2; // Calculate the middle index

if (arr[mid] == target)

return mid; // Return index of target element if found

if (arr[mid] < target)

left = mid + 1; // Adjust left boundary if target is in the right half

else

right = mid - 1; // Adjust right boundary if target is in the left half

}

return -1; // Return -1 if target element is not found

}

int main() {

int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}; // Sorted array

int length = sizeof(arr) / sizeof(arr[0]); // Calculate number of elements in arr

int target = 23; // Element to search for

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

if (result == -1)

printf("Element %d is not present in the array\n", target);

else

printf("Element %d is present at index %d\n", target, result);

return 0;

}

Here`int length = sizeof(arr) / sizeof(arr[0]);`

calculates the number of elements in the array.

: This operator returns the total number of bytes occupied by the array**sizeof(arr)**`arr`

in memory. This size includes all elements of the array multiplied by the size of each element.

: This operator returns the size of the first element of the array**sizeof(arr[0])**`arr`

. Since arrays in C are contiguous blocks of memory, the size of one element (`arr[0]`

) is the same as the size of all other elements in the array.**Division**: By dividing`sizeof(arr)`

by`sizeof(arr[0])`

, we get the number of elements in the array`arr`

. This calculation works because`sizeof(arr)`

gives us the total size of the array in bytes, and`sizeof(arr[0])`

gives us the size of one element. Therefore, the division gives us the number of elements (`n`

) in the array`arr`

.- Example:

`int arr[] = {1, 3, 5, 7, 9};`

`sizeof(arr)`

would typically be`5 * sizeof(int)`

if`int`

occupies 4 bytes in memory (assuming a typical system).`sizeof(arr[0])`

would be`sizeof(int)`

.

Therefore, `sizeof(arr) / sizeof(arr[0])`

would be `5`

, which is the number of elements in the array `arr`

.

## Advantages of `sizeof(arr) / sizeof(arr[0])`

:

**Compile-Time Computation**: This method computes the array size at compile-time, which is efficient and does not require additional runtime calculations.**Works with Statically Allocated Arrays**: It is well-suited for arrays defined statically within the same scope where their size needs to be determined.**Independent of Data Type**: It calculates the number of elements regardless of the data type (`int`

,`char`

, etc.) of the array elements.