C# Algorithm Interview Question: Binary Search

This is the mostly asked question based on search algorithm. In binary search an array is given, and we are asked to search the given number in the array. Source array is already sorted in ascending order.

Logic here is to find the mid point of the array, then check if this mid point have the searched element, if yes, then return that index value. If its not, then based on if searched element is greater or lower than the current mid point value, we find the element in the first or second half of the array.

Below is one way to implement this algorithm. Its time complexity is O(log n).

public int BinarySearch(int[] inputArray, int searchItem, int min, int max)
{
	int mid = min + ((max - min) / 2);
	if (min == max && inputArray[mid] != searchItem)
	{
		return -1;
	}
	if (inputArray[mid] == searchItem)
	{
		return mid;
	}
	else if(searchItem > inputArray[mid])
	{

		return BinarySearch(inputArray, searchItem, mid+1, max);
	}
	else if (searchItem < inputArray[mid])
	{
		return BinarySearch(inputArray, searchItem, min, mid-1);
	}

	return -1;
}