// input array is assumed to be sortedpublic 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<int> _result = new List<int>(); for (int i = start; i <= end; i++) {  _result.Add(arr[i]); } return _result.ToArray();}