Binary Search in C with Best and Worst Time Complexity

What is Binary Search?

Binary search is an algorithm that is used to find an element in a sorted array efficiently. It has a time complexity of O(log n). It means that the time taken by the algorithm grows logarithmically with the size of the input respectively.

Here is an example of how to implement binary search in C.

Example 1:

#include <stdio.h>
int binary_search(int arr[], int n, int x)
{
int low = 0;
int high = n - 1;


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


if (arr[mid] == x)
return mid;
else if (arr[mid] < x)
low = mid + 1;
else
high = mid - 1;
    }


return -1;
}


int main()
{
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 3;


int result = binary_search(arr, n, x);


if (result == -1)
printf("Element not found in array\n");
else
printf("Element found at index %d\n", result);


return 0;
}

Output:

Element found at index 2

Here is another example to explain the same.

Example 2:

#include <stdio.h>
int binarySearch(int array[], int size, int value) {
int low = 0;
int high = size - 1;
int mid;


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


if (array[mid] == value) {
return mid;
        } else if (array[mid] < value) {
low = mid + 1;
        } else {
high = mid - 1;
        }
    }


return -1;
}


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


if (index == -1) {
printf("Value not found\n");
    } else {
printf("Value found at index %d\n", index);
    }


return 0;
}

Output:

Value found at index 4

This implementation takes an array of integers, the size of the array, and the value to search for as input. It returns the index of the value in the array if it is found, or “Element not found in array” if it is not found.

The function uses a binary search algorithm to search for the value in the array. It works by dividing the array into halves and comparing the value at the midpoint of the array with the target value. If the value is equal to the target value, it returns the index. If the value is less than the target value, it searches the right half of the array. If the value is greater than the target value, it searches the left half of the array. This process is repeated until the value is found or it is clear that the value is not present in the array.

Time Complexity of Binary Search in C

The time complexity of binary search in C (or any other language) is O(log n), where n is the size of the input array.

This means that the time taken by the algorithm grows at a logarithmic rate as the size of the input array increases. This makes binary search very efficient for large arrays, as the time taken to search the array increases slowly as the array grows.

For example, if the array has a size of 1,000, it will take at most 10 comparisons to find the value (since log2(1000) is approximately 10). If the array has a size of 1,000,000, it will take at most 20 comparisons to find the value (since log2(1,000,000) is approximately 20).

In contrast, a linear search algorithm, which searches for a value by examining each element of the array one by one, has a time complexity of O(n), meaning that the time taken by the algorithm grows linearly with the size of the input array. This makes linear search less efficient for large arrays.

Best case:

When the element that is being searched for is the first element in the array then the best case time complexity of binary search is O(1).However, in the best case, the time complexity of binary search is O(1). This happens when the element being searched for is the middle element in the array. In this case, the algorithm finds the element in just only one step.

Worst Case:

The worst case time complexity is O(log n) when the element being searched for is not present in the array or is present at the end of the array. This occurs when the element being searched for is not present in the array and the algorithm has to search the entire array.

Overall, binary search is a very efficient algorithm for searching a sorted array and is much faster than linear search, which has a time complexity of O(n).