Binary Search in C

"In computer science, a binary search or half-interval search algorithm finds the position of a specified value (the input "key") within a sorted array.[1][2] In each step, the algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been found so its index, or position, is returned. Otherwise, if the sought 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 input key is greater, on the sub-array to the right. If the remaining array to be searched is reduced to zero, then the key cannot be found in the array and a special "Not found" indication is returned." - Wikipedia

	/** Binary Search locates the position of an item in a sorted list.
	*
	* Divide : It works by dividing the list into two halves and
	* comparing the input value to be searched with the
	* middle element of the list.
	*
	* Conquer : If the input value is equal to the mid value, search
	* is successful. If greater, call binary search only
	* on the greater sub-array of the sorted list and if
	* lesser, call binary search on the lesser sub-array.
	* Continue this until you find the input value or you
	* reach a scenario where no match is found even after
	* the sub-array reduces to a size of 1.
	**/
	#include<stdio.h>
	int main(void)
	{
	int list[20], n, i, search_num, result;
	printf("Enter the size of the array:");
	scanf("%d", &n);
	printf("Enter the elements in the list in ascending order\n");
	for(i = 0; i < n; i++)
	scanf("%d", &list[i]);
	printf("Enter element to be searched:");
	scanf("%d", &search_num);
	result = binary_search(list, n, search_num);
	// binary_search returns -1 if search_num not found
	if(result == -1) {
	printf("No such element in the list.\n");
	printf("Search unsuccessful :-(\n");
	}
	// binary_search returns the position of the search_num
	// if element found in the list
	else {
	printf("Element found at location %d", result);
	printf("of the list(starting from zero)\n");
	}
	return 0;
	}
	int binary_search(int arr[], int size, int search_val)
	{
	int low, high, mid;
	low = 0;
	high = size - 1;
	while(low <= high) {
	mid = (low + high)/2;
	// if search_val = middle element return mid
	if(search_val == arr[mid])
	return mid;
	// if search_val < middle element search lower/lesser
	// half of the sorted list
	else if(search_val < arr[mid])
	high = mid - 1;
	// if search_val > middle element search higher/greater
	// half of the sorted list
	else if(search_val > arr[mid])
	low = mid + 1;
	}
	return -1;
	}

view raw binary_search.c hosted with ❤ by GitHub

Written by Munia Balayil