Monday, February 2, 2015

Find local min in list of distinct numbers

Given a list of distinct numbers, find the number is smaller 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.

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?

6 comments:

  1. I think your code doesn't pass {1, 2, 3, 5, 4, 7};

    ReplyDelete
    Replies
    1. it does, it return 0 index. which is 1

      Delete
    2. start = 0, end = 5, mid = 2
      start = 0, end = 2, mid = 1,
      start = 0, end = 1
      exit loop
      return start = 0

      Delete
    3. but index 0(value 1) is not the answer, answer should be index 4(value 4).

      Delete
    4. Actually 1 and 4 are all local min., That is the reason the question says "return any of local mins"

      Delete
    5. ok, 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