# Java solution: partition first, then binary search

• I think most people are doing binary search straight on the rotated array, but it is not intuitive to me, because I think binary search is for sorted array only. I made an attempt to do a partition of the rotated array first, which returns the index of the pivot point. After that, I perform a binary search on the sorted segment in the rotated array.

``````// find the partition point for segment of increasing order
public int searchInRotated(int[] nums, int target) {

if (nums == null || nums.length < 1) return -1;
int result = -1;

int pivotIndex = partition(nums);
System.out.println("pivot index: " + pivotIndex);

int lo = 0, hi = 0;
if (nums[pivotIndex] == target) {
return pivotIndex;
} else if (nums[pivotIndex] > target) {
hi = pivotIndex;
lo = 0;
} else {
lo = pivotIndex;
hi = nums.length - 1;
}

// binary search
while (lo + 1 < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
hi = mid;
} else {
lo = mid;
}
}

if (nums[lo] == target) {
return lo;
} else if (nums[hi] == target) {
return hi;
}

return result;
}

// return the index of the pivot point
private int partition(int[] numbers) {

// make a clone
int[] nums = Arrays.copyOfRange(numbers, 0, numbers.length);

int pivot = nums[0];
int left = 0, right = nums.length - 1;
while (left < right) {
while (left < right && nums[right] >= pivot) {
right--;
}
nums[left] = nums[right];

while (left < right && nums[left] <= pivot) {
left++;
}
nums[right] = nums[left];
}

nums[left] = pivot; // place the pivot value at the partitioning point

return left;
}

``````

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