Binary search is a searching algorithm that efficiently searches a sorted array or list by repeatedly dividing the search interval in half. The algorithm compares the target element with the middle element of the array or list. If the target element is equal to the middle element, the search is complete. If the target element is less than the middle element, the search continues on the lower half of the array. If the target element is greater than the middle element, the search continues on the upper half of the array.
In C language, the binary search algorithm can be implemented using a loop that iteratively halves the search interval until the target element is found or the search interval is empty.
Here is an example implementation of binary search in C language:
int binarySearch(int arr[], int n, int x) {
int low = 0, 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;
}
In this implementation, arr is the sorted array of elements to be searched, n is the size of the array, and x is the element to be searched. The binarySearch function uses low and high variables to represent the search interval. The search interval is repeatedly halved until the target element is found or the search interval is empty. The mid variable is the index of the middle element in the search interval. If the target element is equal to the middle element, the search is complete. If the target element is less than the middle element, the search continues on the lower half of the search interval. If the target element is greater than the middle element, the search continues on the upper half of the search interval. If the target element is not found, the function returns -1.
