Binary search is a searching algorithm used to find the position of an element in a sorted array. The algorithm works by repeatedly dividing the search interval in half until the target element is found or the search interval is empty. Binary search is faster than linear search, especially for large arrays, as it reduces the number of iterations required to find the target element.
Here is an example of binary search in C using an iterative approach:
int binarySearch(int array[], int x, int low, int high) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (array[mid] == x)
return mid;
if (array[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
This function takes an array, the target element x, and the lower and upper bounds of the search interval as input. It returns the index of the target element if it is found, or -1 if it is not present in the array. The function works by repeatedly dividing the search interval in half and comparing the middle element to the target element. If the middle element is equal to the target element, the function returns its index. If the middle element is less than the target element, the search interval is shifted to the right half of the array. If the middle element is greater than the target element, the search interval is shifted to the left half of the array. The process repeats until the target element is found or the search interval is empty.
Note that the C standard library provides a function called bsearch() that uses the binary search algorithm to find an element in a sorted array. This function takes a pointer to the target element, a pointer to the first element of the array, the number of elements in the array, the size of each element, and a comparison function as input. The comparison function is used to compare elements of the array to the target element. The bsearch() function returns a pointer to the matching element if it is found, or NULL if it is not present in the array.
