Sun Apr 18 2021
Binary Search
Binary search is one of the fundamental algorithms in computer science. It relies on a divide and conquer strategy to find a value within an already-sorted collection. For binary search, the array should be arranged in ascending or descending order. In each step, the algorithm compares the search key value with the key value of the middle element of the array. If the keys match, then a matching element has been found and its index, or position, is returned. Otherwise, if the search key is less than the middle element's key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the search key is greater, on the sub-array to the right. If the remaining array to be searched is empty, then the key cannot be found in the array and a special "not found" indication is returned.
log2(N)-1 is the expected number of problems in an average successful search, and the worst case is log2(N). If the list is empty, no problems at all are made. Thus binary search is a logarithmic algorithm and executes in O(log N) time. In most cases it is considerably faster than a linear search. It can be implemented using iteration, or recursion.
File Name: binary-search-algorithm.c
int binary_search(int A[], int key, int imin, int imax) {
/* test if array is empty */
if (imax < imin)
/* set is empty, so return value showing not found */
return KEY_NOT_FOUND;
else {
/* calculate midpoint to cut set in half */
int imid = midpoint(imin, imax);
/* three-way comparison */
if (A[imid] > key)
/* key is in lower subset */
return binary_search(A, key, imin, imid-1);
else if (A[imid] < key)
/* key is in upper subset */
return binary_search(A, key, imid+1, imax);
else
/* key has been found */
return imid;
}
}