int SearchInRotatedSortedArray(int array[], int low, int high, int target) 
{
    while(low <= high)
    {
        int mid = (low + high) / 2;
        if (target < array[mid])
            if (array[mid] < array[high])//the higher part is sorted
                high = mid - 1; //the target would only be in lower part
            else //the lower part is sorted
				if(target < array[low])//the target is less than all elements in low part
					low = mid + 1;
				else
                    high = mid - 1;

        else if(array[mid] < target)
            if (array[low] < array[mid])// the lower part is sorted
                low = mid + 1; //the target would only be in higher part
            else //the higher part is sorted
               if (array[high] < target)//the target is larger than all elements in higher part
                    high = mid - 1;
                else
                    low = mid + 1;
        else //if(array[mid] == target)
            return mid;
    }

    return -1;
}

#include <iostream>

using namespace std;

int main(int argc, char** argv)
{
    int a[] = { 7, 11, 13, 17, 2, 3, 5};
    cout << SearchInRotatedSortedArray(a, 0, 6, 1);

    return 0;
}