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?
I think your code doesn't pass {1, 2, 3, 5, 4, 7};
ReplyDeleteit does, it return 0 index. which is 1
Deletestart = 0, end = 5, mid = 2
Deletestart = 0, end = 2, mid = 1,
start = 0, end = 1
exit loop
return start = 0
but index 0(value 1) is not the answer, answer should be index 4(value 4).
DeleteActually 1 and 4 are all local min., That is the reason the question says "return any of local mins"
Deleteok, I think this is what the question said about "edges". And I saw so many people wrote the similar code. But this sounds cheat.
Delete