Normal Binary Search
if ( arr [ mid ] == x ) return mid ; else if ( x . CompareTo ( arr [ mid ] ) < 0 ) return binarySearch ( arr , low , mid - 1 , x ) ; else return binarySearch ( arr , mid + 1 , high , x ) ; } static int sparseSearch ( string [ ] arr , string x , int n ) { return binarySearch ( arr , 0 , n - 1 , x ) ; }