This problem can also extend to different problem, given a list of numbers, find the number is not bigger than its adjacent numbers, if the number is at the start or end of the list, then this number is smaller than its neighbor only.
The solution is to do binary search:
//find local min
public static int findLocalMin(int[] nums){
if(nums.length == 0)
return -1;
if(nums.length <= 2)
return 0;
int start = 0, end = nums.length -1;
while(start<end-1){
int mid = (start + end)>>>1;
if(nums[mid]<nums[mid-1] && nums[mid]<nums[mid+1]){
return mid;
}else if(nums[mid] > nums[mid-1])
end = mid;
else
start = mid;
}
if(nums[start] < nums[end])
return start;
else
return end;
}
A question for the reader, can you figure out a solution to find local min in 2D matrix?
