Search in an almost sorted array | C # program to find an element in an almost sorted array ; A recursive binary search based function . It returns index of x in given array arr [ l . . r ] is present , otherwise - 1 ; If the element is present at one of the middle 3 positions ; If element is smaller than mid , then it can only be present in left subarray ; Else the element can only be present in right subarray ; We reach here when element is not present in array ; Driver code
using System ; class GFG { int binarySearch ( int [ ] arr , int l , int r , int x ) { if ( r >= l ) { int mid = l + ( r - l ) / 2 ; if ( arr [ mid ] == x ) return mid ; if ( mid > l && arr [ mid - 1 ] == x ) return ( mid - 1 ) ; if ( mid < r && arr [ mid + 1 ] == x ) return ( mid + 1 ) ; if ( arr [ mid ] > x ) return binarySearch ( arr , l , mid - 2 , x ) ; return binarySearch ( arr , mid + 2 , r , x ) ; } return - 1 ; } public static void Main ( ) { GFG ob = new GFG ( ) ; int [ ] arr = { 3 , 2 , 10 , 4 , 40 } ; int n = arr . Length ; int x = 4 ; int result = ob . binarySearch ( arr , 0 , n - 1 , x ) ; if ( result == - 1 ) Console . Write ( " Element ▁ is ▁ not ▁ present ▁ in ▁ array " ) ; else Console . Write ( " Element ▁ is ▁ present ▁ at ▁ index ▁ " + result ) ; } }