# 1ms Java (n + log n) solution by finding pivot first

• 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;
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.