Binary Search Algorithm

Generally, to find a value in unsorted array, we should  choose:
1 Take a look through elements of an array one by one, until searched value is found. If required value doesn't exists in  our array, then we will pass all array, all elements. In average, complexity of such an algorithm is  O(n) n- count of elements.
2. Sort array  using  any in place sort algorithms, QuickSort for instance, and then apply Binary Search algorithm.


Algorithm

Algorithm is very simple. It can be done either recursively or iteratively:

1. get the middle element;
2. if the middle element equals to the searched value, the algorithm stops;
3. otherwise, two cases are possible:

• searched value is less, than the middle element. In this case, go to the step 1 for the part of the array, before middle element.
• searched value is greater, than the middle element. In this case, go to the step 1 for the part of the array, after middle element.

I decided  to implement it recursive way with a few enhancements.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

public class BinarySearch { public int Search(List A, T val) where T : IComparable { if (A == null || A.Count == 0) return -1; return InnerSearch(A, val, 0, A.Count() - 1); } private int InnerSearch(List A, T val, int min, int max) where T : IComparable { int middle = (min + max) / 2; if (max < min || min > max) return -1; if (A[middle].CompareTo(val) == 0) return middle; if (middle == A.Count() - 1) return -1; if (A[min].CompareTo(val) == 0) return min; if (A[max].CompareTo(val) == 0) return max; else if (A[middle].CompareTo(val) > 0) return InnerSearch(A, val, min+1, middle - 1); else return InnerSearch(A, val, middle + 1, max-1); } }