Binary Search

Binary search is an algorithm for finding the location of an element in a sorted list. First, it checks the middle element of the sort list; if that element is equal to the sought value then the location has been found; Othewise, the lower half or upper half is chosen for next searching based on the sought value less than or greater than the middle element. By doing so, this binary search reduces the number of elements to be checked by a factor of two each time searching and find the element in logarithmic time. Binary Search implemented in C.

int binary_search(int sorted_list[], int low, int high, int element) {
while (low <= high) {
int middle = low + (high - low)/2;
if (element > sorted_list[middle])
low = middle + 1;
else if (element < sorted_list[middle])
high = middle - 1;
else
return middle;
}
return -1;
}

Binary Search in using recursion technique.

int binary_search(int sorted_list[], int low, int high, int element) {
if (high < low)
return -1;
int middle = low + (high - low)/2;
if (element < sorted_list[middle])
return binary_search(sorted_list, low, middle-1, element);
else if (element > sorted_list[middle])
return binary_search(sorted_list, middle+1, high, element);
else
return middle;
}