# Binary search in C

Binary search in C language to find an element in a sorted array. If the array isn't sorted, you must sort it using a sorting technique such as merge sort. If the element to search is present in the list, then we print its location. The program assumes that the input numbers are in ascending order.

## Binary search program in C

#include <stdio.h>

int main()
{
int c, first, last, middle, n, search, array;

printf("Enter number of elements\n");
scanf("%d", &n);

printf("Enter %d integers\n", n);

for (c = 0; c < n; c++)
scanf("%d", &array[c]);

printf("Enter value to find\n");
scanf("%d", &search);

first = 0;
last = n - 1;
middle = (first+last)/2;

while (first <= last) {
if (array[middle] < search)
first = middle + 1;
else if (array[middle] == search) {
printf("%d found at location %d.\n", search, middle+1);
break;
}
else
last = middle - 1;

middle = (first + last)/2;
}
if (first > last)

return 0;
}

Output of program: C program for linear search

Binary search is faster than the linear search. Its time complexity is O(log(n)), while that of the linear search is O(n). However, the list should be in ascending/descending order, hashing is rapid than binary search and perform searches in constant time.

## Binary search in C using recursion

#include <stdio.h>

int binarySearch(int [], int, int, int);

int main()
{
int c, first, last, n, search, array, index;

printf("Enter number of elements\n");
scanf("%d", &n);

printf("Enter %d integers\n", n);

for (c = 0; c < n; c++)
scanf("%d", &array[c]);

printf("Enter value to find\n");
scanf("%d", &search);

first = 0;
last = n - 1;

index = binarySearch(array, first, last, search);

if (index == -1)
else
printf("%d is present at location %d.\n", search, index + 1);

return 0;
}

int binarySearch(int a[], int s, int e, int f) {
int m;

return -1;

m = (s + e)/2;

if (a[m] == f)  // element found
return m;
else if (f > a[m])
return binarySearch(a, m+1, e, f);
else
return binarySearch(a, s, m-1, f);
}

We pass four arguments to binarySearch function: array its first and the last index, element to search.

You can also search an element in a part of the array if required.