Binary Search - C#
Join the DZone community and get the full member experience.
Join For FreeBinary Search - C# (input array is assumed to be sorted)
Efficiency: O(log n)
// input array is assumed to be sorted
public int BinarySearch(int[] arr, int x)
{
if (arr.Length == 0)
return -1;
int mid = arr.Length / 2;
if (arr[mid] == x)
return mid;
if (x < arr[mid])
return BinarySearch(GetSubArray(arr, 0, mid - 1), x);
else
{
int _indexFound = BinarySearch(GetSubArray(arr, mid + 1, arr.Length - 1), x);
if (_indexFound == -1)
return -1;
else
return mid + 1 + BinarySearch(GetSubArray(arr, mid + 1, arr.Length - 1), x);
}
}
public int[] GetSubArray(int[] arr, int start, int end)
{
List _result = new List();
for (int i = start; i <= end; i++)
{
_result.Add(arr[i]);
}
return _result.ToArray();
}
Efficiency (statistics)
Data structure
Opinions expressed by DZone contributors are their own.
Comments