Here is my n + log(n) solution, that finds the pivot first before establishing the right bounds for binary search. Surprisingly it ran in only `1ms`

, which turned out to be faster than the (smarter and in my opinion cleaner solution, which ran in `2ms`

, one of the top voted): https://leetcode.com/discuss/41134/java-ac-solution-using-once-binary-search

My guess on this is that the other solution has to check if `nums[mid]`

is the target on every iteration, hence slowing down the search, see: Deffered Detection of Equality on Wikipedia (https://en.wikipedia.org/wiki/Binary_search_algorithm#Deferred_detection_of_equality)

Here is my code:

```
// n + log n implementation
// since we need to find the pivot first
public int search(int[] nums, int target) {
int pivot = 1;
while(pivot <= nums.length - 1 && nums[pivot] > nums[pivot -1])
pivot++;
//shift back to highest value
pivot--;
//search space is on the left side of pivot
int low = 0;
int high = pivot;
//search space is on the right side of pivot
if((pivot != nums.length - 1 || pivot == 0) && nums[0] > target)
{
low = pivot + 1;
high = nums.length - 1;
}
// System.out.println("LOW : " + low + ", PIVOT : " + pivot + " , HIGH: " + high);
while(low < high)
{
int mid = low + (high - low) / 2;
if(nums[mid] < target)
low = mid + 1;
else
high = mid;
}
if(low < nums.length && nums[low] == target) //avoid index out of bounds on unfound number
return low;
return -1;
}
}
```