Specific Sorted Array Search -

you given 1 sorted array, example:

1 2 3 5 7 9 10 12 13 15 17 

then, split @ 1 (random) part 2 arrays, example:

1 2 3 5 7 9 10 12 13 15 17 

then, merged again, this:

10 12 13 15 17 1 2 3 5 7 9 

it asked write function searches through new array specific element , returns position:

int find(int* newarray, int arraylength, int elementtofind); 

it asked optimal possible.

my solution based on binary search. each time half picked, algorithm checks whether half bigger begin.

• if case, items between begin , half have sorted. algorithm checks whether needed item in range *begin-*half
  • if search conducted in place (there possibility use normal binary search in such case)
  • otherwise search have conducted between half , end

• if half lover begin there have "slope" in range, thus

  • if item outside range *begin , *half algorithm should search between begin , half

  • if item inside range *begin , *half algorithm should search between half , end

    int* find2(int* begin, int* end, int elementtofind) {     int* half = begin + (end-begin + 1)/2;      if(*begin == elementtofind)     {         return begin;     }      if(*half > *begin)     {         if(*half > elementtofind && *begin < elementtofind)         {             return find2(begin, half, elementtofind);         }         else         {             return find2(half, end, elementtofind);         }     }     else     {         if(*half <= elementtofind && *begin > elementtofind)         {             return find2(half, end, elementtofind);         }         else         {             return find2(begin, half, elementtofind);         }     } }  int find(int* newarray, int arraylength, int elementtofind) {     return find2(newarray, newarray+arraylength-1, elementtofind) - newarray; }