# Java Solution, Naive and Optimized Method

• The naive way to find minimum value is to treat the array as unsorted array and traverse the whole array. It results in O(n) complexity.

``````public class Solution {
public int findMin(int[] nums) {
int min = nums[0];
for(int i = 1; i < nums.length; i++){
if(min > nums[i]) min = nums[i];
}
return min;
}
}
``````

But since the array is partially sorted, we can do binary search to find at what index the rotation started.
To do this, we divide array "nums" into 2 sub-array bounded by left <= mid < right.
The rotation is located in either [left, mid] or [mid+1, right] in which the array is not sorted. And then we process the sub-array that is not sorted to find rotation index. The time complexity is O(lg n)

``````public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
int mid = 0;

while(left < right) {

//the subarray [left, right] is sorted perfectly
if (nums[left] < nums[right]) return nums[left];

mid = (left + right)>>1;

if(nums[mid] >= nums[left]) {
//subarray [left, mid] is sorted
//but we have checked above that nums[left] is not the smallest element
//so continue with subarray [mid + 1, right]
left = mid + 1;
} else {
//subarray [mid + 1, right] is sorted
//so the rotation is in [left, mid]
right = mid;
}
}

return nums[left];
}``````

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