Binary Search Solution in Java


  • 0
    J

    Hi:
    This is my accepted solution, which uses binary search. O(logN).

    public int findMin(int[] num) {
        int low = 0;
        int high = num.length - 1;
        if (num[low] < num[high]) { // Not rotated
            return num[low];
        }
        while (true) {
            if (high == low) { // Cases like [1]
                return num[low];
            } else if (high - 1 == low) {
                return Math.min(num[high], num[low]);
            }
            int mid = (low + high) / 2;
            if (num[low] > num[mid]) {
                high = mid;
            } else {
                low = mid;
            }
        }
    }
    

    Reason why it works:
    Since we are looking for the smallest, when we see the arr[0] > arr[mid], then the pivot must be somewhere between these two elements. Otherwise it's in the other half. Apply this recursively and we will get the solution. Although it's accepted, I am still not 100% clear about the edge cases, so please correct me if any part of this code is unnecessary. Thanks!


  • 2
    Z

    The same idea but I think it is simplier. We just need to stop when the size of the interval is 2.

    public class Solution {
        public int findMin(int[] num) {
            int n = num.length;
            if(num[0] < num[n-1])
                return num[0];
    
            int l = 0, r = n-1;
    
            while (r-l > 1) {
                int m = (l+r)/2;
                if(num[l] < num[m])
                    l = m;
                else
                    r = m;
            }
    
            return Math.min(num[l], num[r]);
        }
    }

  • 0
    A

    This looks good, but should take care of edge cases:

    1. n = num.length == 0; your code will throw exception.
    2. n = num.length == 1; your code will work, maybe by luck :)

  • 0
    Z

    I did.

    1. When num.length == 0. The signature "public int findMin(int[] num)" of the method requires you to return "int". It is value type. Therefore the invariant is if you return a value it should present in the array. But when the array is empty it breaks the invariant. If it had been "public Integer findMin(int[] num)" where "Integer" is reference type then you could have been able to return "null" as a value. Therefore the only case for empty array is throwing an exception. My solution throws ArrayIndexOutOfBoundsException:

      @Test(expected = java.lang.ArrayIndexOutOfBoundsException.class)
      public void test04() {
      new Solution().findMin(new int[]{});
      }

    Which I think is okay for OJ solutions, but for "public production middleware" functions I would add validation num.length == 0 and throw IllegalArgumentException:

    if(num.length == 0)
    	throw new IllegalArgumentException("num");
    

    But you should throw an exception.

    1. When num.length == 1 I also checked:

      @Test
      public void test03() {
      int[] num = {1};

       assertEquals(1, new Solution().findMin(num));
      

      }

    It works because it enters neither "if" nor "while" and only parts which works is "return Math.min(num[l], num[r]);" which compares the value with itself.
    I did this intentionally in order to avoid extra checks like this:

    if(num.legth == 1)
    	return num[0];
    

    I hope it helps.


Log in to reply
 

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